optimize std::max early

we currently produce very bad code on loops using std::vector as a stack, since
we fail to inline push_back which in turn prevents SRA and we fail to optimize
out some store-to-load pairs.

I looked into why this function is not inlined and it is inlined by clang.  We
currently estimate it to 66 instructions and inline limits are 15 at -O2 and 30
at -O3.  Clang has similar estimate, but still decides to inline at -O2.

I looked into reason why the body is so large and one problem I spotted is the
way std::max is implemented by taking and returning reference to the values.

  const T& max( const T& a, const T& b );

This makes it necessary to store the values to memory and load them later
and max is used by code computing new size of vector on resize.

We optimize this to MAX_EXPR, but only during late optimizations.  I think this
is a common enough coding pattern and we ought to make this transparent to
early opts and IPA.  The following is easist fix that simply adds phiprop pass
that turns the PHI of address values into PHI of values so later FRE can
propagate values across memory, phiopt discover the MAX_EXPR pattern and DSE
remove the memory stores.

gcc/ChangeLog:

	PR tree-optimization/109811
	PR tree-optimization/109849
	* passes.def: Add phiprop to early optimization passes.
	* tree-ssa-phiprop.cc: Allow clonning.

gcc/testsuite/ChangeLog:

	PR tree-optimization/109811
	PR tree-optimization/109849
	* gcc.dg/tree-ssa/phiprop-1.c: New test.
	* gcc.dg/tree-ssa/pr21463.c: Adjust template.

diff --git a/gcc/passes.def b/gcc/passes.def
index c9a8f19747b2b4ee27c8f99802638db2164109ba..faa5208b26b470eb0ec83461725658a3e586d0da 100644 (file)
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -88,6 +88,8 @@ along with GCC; see the file COPYING3.  If not see
          /* pass_build_ealias is a dummy pass that ensures that we
             execute TODO_rebuild_alias at this point.  */
          NEXT_PASS (pass_build_ealias);
+         /* Do phiprop before FRE so we optimize std::min and std::max well.  */
+         NEXT_PASS (pass_phiprop);
          NEXT_PASS (pass_fre, true /* may_iterate */);
          NEXT_PASS (pass_early_vrp);
          NEXT_PASS (pass_merge_phi);

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/phiprop-1.c b/gcc/testsuite/gcc.dg/tree-ssa/phiprop-1.c
new file mode 100644 (file)
index 0000000..b448e83
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/phiprop-1.c
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -fdump-tree-phiprop1-details -fdump-tree-release_ssa" } */
+int max(int a, int b)
+{
+        int *ptr;
+        if (a > b)
+          ptr = &a;
+        else
+          ptr = &b;
+        return *ptr;
+}
+
+/* { dg-final { scan-tree-dump-times "Inserting PHI for result of load" 1 "phiprop1"} } */
+/* { dg-final { scan-tree-dump-times "MAX_EXPR" 1 "release_ssa"} } */

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr21463.c b/gcc/testsuite/gcc.dg/tree-ssa/pr21463.c
index ed0829a038c48d9b7a223ebafb80fc6a43dcef26..c6f1226d6834565c3dda14b5b57c025abf7bfc9b 100644 (file)
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr21463.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr21463.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O -fdump-tree-phiprop-details" } */
+/* { dg-options "-O -fdump-tree-phiprop1-details" } */
 
 struct f
 {
@@ -16,4 +16,4 @@ int g(int i, int c, struct f *ff, int g)
   return *t;
 }
 
-/* { dg-final { scan-tree-dump-times "Inserting PHI for result of load" 1 "phiprop" } } */
+/* { dg-final { scan-tree-dump-times "Inserting PHI for result of load" 1 "phiprop1" } } */

diff --git a/gcc/tree-ssa-phiprop.cc b/gcc/tree-ssa-phiprop.cc
index 3cb4900b6be526d13a30833d816aa9f0c907fdab..5dc505df420889feec51349df0722630e3209cb1 100644 (file)
--- a/gcc/tree-ssa-phiprop.cc
+++ b/gcc/tree-ssa-phiprop.cc
@@ -476,6 +476,7 @@ public:
   {}
 
   /* opt_pass methods: */
+  opt_pass * clone () final override { return new pass_phiprop (m_ctxt); }
   bool gate (function *) final override { return flag_tree_phiprop; }
   unsigned int execute (function *) final override;