New IPA ICF pass.
IPA ICF: new tests added, many tests were fixed.
Pass cleaned-up.

First phase of notes merged.
IPA ICF: attribute comparison enhanced.

LHS noreturn check removed.
Merge remote-tracking branch 'parent/master' into ipa-icf-pass
IPA ICF: pass cleaned-up.
IPA ICF: condition fixed.
IPA ICF: pass fixed.
IPA ICF: ipa-prop decl args API used.

Thunk COMDAT skip reverted, local redirection deletion added.
Merge remote-tracking branch 'parent/master' into ipa-icf-pass
IPA ICF: semi-working version.
IPA ICF: cgraph_make_wrapper fixed. Pass TODOs removed.
Merge remote-tracking branch 'parent/master' into ipa-icf-pass
cgraphunit.c: revert modification
New Identical Code Folding IPA pass

Hello,
  I am sorry for wrong reply address in previously sent thread. After working for quite a long time, I would like to introduce new IPA pass. Goal of the pass is to merge semantically equivalent functions and read-only variables.
  If we prove that a function A is an equivalent to a function B, depending on circumstances, an alias, thunk or a function redirection is created.

  The optimization is inspired by Microsoft /OPT:ICF optimization (http://msdn.microsoft.com/en-us/library/bxwfs976.aspx) that merges COMDAT sections with each function reside in a separate section.
  Apart from that, GOLD linker implemented equivalent implementation for GNU toolchain: SAFE ICF (http://research.google.com/pubs/pub36912.html). Both implementations suffer from a collection of functions where an address was taken for comparison purpose. GOLD linker adds more conservative --icf=safe option.

  You may ask, why the GNU GCC does need such a new optimization. The compiler, having simply better knowledge of a compiled source file, is capable of reaching better results, especially if Link-Time optimization is enabled. Apart from that, GCC implementation adds support for read-only variables like construction vtables (mentioned in: http://hubicka.blogspot.cz/2014/02/devirtualization-in-c-part-3-building.html).

  The pass is capable of building GIMP, Inkscape and Firefox with enabled LTO. Majority of issues connected to testsuite has been fixed, there is a few of IPA tests I need to consult with Jan, how to fix it correctly.

  Statistics about the pass:
  Inkscape: 11.95 MB -> 11.44 MB (-4.27%)
  Firefox: 70.12 MB -> 70.12 MB (-3.07%)

  SPEC 2K6 statistics show how many equivalent functions (and variables) are proved by GOLD and GCC ICF:
  +----------------+----------+---------+------------+------------------+--------------+--------------+-------------+
  | SPEC           | GOLD ICF | IPA ICF | difference | difference perc. | intersection | Just in GOLD | Just in ICF |
  +----------------+----------+---------+------------+------------------+--------------+--------------+-------------+
  | 400.perlbench  |       26 |      53 |         27 |          203.85% |           26 |            0 |          27 |
  | 401.bzip2      |        0 |       1 |          1 |            0.00% |            0 |            0 |           1 |
  | 403.gcc        |       88 |     223 |        135 |          253.41% |           81 |            7 |         142 |
  | 410.bwaves     |        0 |       0 |          0 |            0.00% |            0 |            0 |           0 |
  | 416.gamess     |        9 |      23 |         14 |          255.56% |            9 |            0 |          14 |
  | 429.mcf        |        0 |       0 |          0 |            0.00% |            0 |            0 |           0 |
  | 433.milc       |        0 |       8 |          8 |            0.00% |            0 |            0 |           8 |
  | 434.zeusmp     |        0 |       1 |          1 |            0.00% |            0 |            0 |           1 |
  | 436.cactusADM  |       19 |      55 |         36 |          289.47% |           14 |            5 |          41 |
  | 437.leslie3d   |        0 |       0 |          0 |            0.00% |            0 |            0 |           0 |
  | 444.namd       |        0 |       0 |          0 |            0.00% |            0 |            0 |           0 |
  | 445.gobmk      |        0 |     332 |        332 |            0.00% |            0 |            0 |         332 |
  | 453.povray     |       73 |      93 |         20 |          127.40% |           60 |           13 |          33 |
  | 454.calculix   |        3 |       6 |          3 |          200.00% |            3 |            0 |           3 |
  | 456.hmmer      |        0 |       1 |          1 |            0.00% |            0 |            0 |           1 |
  | 458.sjeng      |        0 |       1 |          1 |            0.00% |            0 |            0 |           1 |
  | 459.GemsFDTD   |        0 |       0 |          0 |            0.00% |            0 |            0 |           0 |
  | 462.libquantum |        0 |       0 |          0 |            0.00% |            0 |            0 |           0 |
  | 464.h264ref    |        0 |       4 |          4 |            0.00% |            0 |            0 |           4 |
  | 470.lbm        |        0 |       0 |          0 |            0.00% |            0 |            0 |           0 |
  | 471.omnetpp    |      134 |     179 |         45 |          133.58% |          127 |            7 |          52 |
  | 473.astar      |        0 |       1 |          1 |            0.00% |            0 |            0 |           1 |
  | 481.wrf        |       51 |      75 |         24 |          147.06% |           50 |            1 |          25 |
  | 482.sphinx3    |        0 |       1 |          1 |            0.00% |            0 |            0 |           1 |
  +----------------+----------+---------+------------+------------------+--------------+--------------+-------------+
  | TOTAL          |      403 |    1057 |        654 |          262.28% |          370 |           33 |         687 |
  +----------------+----------+---------+------------+------------------+--------------+--------------+-------------+

  I've been testing the pass on a QEMU Gentoo virtual machine and I will bring stats as soon as possible.

  There are still unresolved issues connected to correct debugging. I am not familiar with DWARF extensions, but it looks
  there is a solution that can be applied to the pass: http://wiki.dwarfstd.org/index.php?title=ICF ?

  I tried to create equivalent functions foo and bar, merged by ICF GOLD. Function bar is removed from .text section, but gdb
  can put a breakpoint to the function, where content of function foo is displayed. I think this is acceptable behavior.

  I expect many comments related to pass, but I hope effort invested by me a Honza will be transformed to acceptation to trunk.

  Martin

(please ignore this diff)
Existing call graph infrastructure enhancement

Hi,
    this small patch prepares remaining needed infrastructure for the new pass.

Changelog:

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

	* ipa-utils.h (polymorphic_type_binfo_p): Function marked external
	instead of static.
	* ipa-devirt.c (polymorphic_type_binfo_p): Likewise.
	* ipa-prop.h (count_formal_params): Likewise.
	* ipa-prop.c (count_formal_params): Likewise.
	* ipa-utils.c (ipa_merge_profiles): Be more tolerant if we merge
	profiles for semantically equivalent functions.
	* passes.c (do_per_function): If we load body of a function during WPA,
	this condition should behave same.
	* varpool.c (ctor_for_folding): More tolerant assert for variable
	aliases created during WPA.
IPA ICF pass

Hello,
   this is core of IPA ICF patchset. It adds new pass and registers all needed stuff related to a newly introduced interprocedural optimization.

Algorithm description:
  In LGEN, we visit all read-only variables and functions. For each symbol, a hash value based on e.g. number of arguments,
  number of BB, GIMPLE CODES is computed (similar hash is computed for read-only variables). This kind of information is streamed
  for LTO.

  In WPA, we build congruence classes for all symbols having a same hash value. For functions, these classes are subdivided in WPA by argument type comparison. Each reference (a call or a variable reference) to another semantic item candidate is marked and stored for further congruence class reduction (similar algorithm as Value Numbering:  www.cs.ucr.edu/~gupta/teaching/553-07/Papers/value.pdf).

  For every congruence class of functions with more than one semantic function, we load function body. Having this information, we can
  process complete semantic function equality and subdivide such congruence class. Read-only variable class members are also deeply compared.

  After that, we process Value numbering algorithm to do a final subdivision. Finally, all items belonging to a congruence class with more than one
  item are merged.

Martin

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.
Existing tests fix

Hi,
  many tests rely on a precise number of scanned functions in a dump file. If IPA ICF decides to merge some function and(or) read-only variables, counts do not match.

Martin

Changelog:

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

	* c-c++-common/rotate-1.c: Text
	* c-c++-common/rotate-2.c: New test.
	* c-c++-common/rotate-3.c: Likewise.
	* c-c++-common/rotate-4.c: Likewise.
	* g++.dg/cpp0x/rv-return.C: Likewise.
	* g++.dg/cpp0x/rv1n.C: Likewise.
	* g++.dg/cpp0x/rv1p.C: Likewise.
	* g++.dg/cpp0x/rv2n.C: Likewise.
	* g++.dg/cpp0x/rv3n.C: Likewise.
	* g++.dg/cpp0x/rv4n.C: Likewise.
	* g++.dg/cpp0x/rv5n.C: Likewise.
	* g++.dg/cpp0x/rv6n.C: Likewise.
	* g++.dg/cpp0x/rv7n.C: Likewise.
	* gcc.dg/ipa/ipacost-1.c: Likewise.
	* gcc.dg/ipa/ipacost-2.c: Likewise.
	* gcc.dg/ipa/ipcp-agg-6.c: Likewise.
	* gcc.dg/ipa/remref-2a.c: Likewise.
	* gcc.dg/ipa/remref-2b.c: Likewise.
	* gcc.dg/pr46309-2.c: Likewise.
	* gcc.dg/torture/ipa-pta-1.c: Likewise.
	* gcc.dg/tree-ssa/andor-3.c: Likewise.
	* gcc.dg/tree-ssa/andor-4.c: Likewise.
	* gcc.dg/tree-ssa/andor-5.c: Likewise.
	* gcc.dg/vect/no-vfa-pr29145.c: Likewise.
	* gcc.dg/vect/vect-cond-10.c: Likewise.
	* gcc.dg/vect/vect-cond-9.c: Likewise.
	* gcc.dg/vect/vect-widen-mult-const-s16.c: Likewise.
	* gcc.dg/vect/vect-widen-mult-const-u16.c: Likewise.
	* gcc.dg/vect/vect-widen-mult-half-u8.c: Likewise.
	* gcc.target/i386/bmi-1.c: Likewise.
	* gcc.target/i386/bmi-2.c: Likewise.
	* gcc.target/i386/pr56564-2.c: Likewise.
	* g++.dg/opt/pr30965.C: Likewise.
	* g++.dg/tree-ssa/pr19637.C: Likewise.
	* gcc.dg/guality/csttest.c: Likewise.
	* gcc.dg/ipa/iinline-4.c: Likewise.
	* gcc.dg/ipa/iinline-7.c: Likewise.
	* gcc.dg/ipa/ipa-pta-13.c: Likewise.
New tests introduction

Hi,
   this is a new collection of tests for IPA ICF pass.

Martin

Changelog:

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

	* gcc/testsuite/g++.dg/ipa/ipa-se-1.C: New test.
	* gcc/testsuite/g++.dg/ipa/ipa-se-2.C: Likewise.
	* gcc/testsuite/g++.dg/ipa/ipa-se-3.C: Likewise.
	* gcc/testsuite/g++.dg/ipa/ipa-se-4.C: Likewise.
	* gcc/testsuite/g++.dg/ipa/ipa-se-5.C: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-1.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-10.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-11.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-12.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-13.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-14.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-15.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-16.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-17.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-18.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-19.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-2.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-20.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-21.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-22.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-23.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-24.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-25.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-26.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-27.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-28.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-3.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-4.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-5.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-6.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-7.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-8.c: Likewise.
	* gcc/testsuite/gcc.dg/ipa/ipa-se-9.c: Likewise.
Merge remote-tracking branch 'parent/master' into ipa-icf-pass