[RFA,tree-optimization/90037] Cleanup const/copies between DOM and erroneous path isolation

As discussed in the BZ, this patch addresses the false positive warning
by cleaning up the const/copy propagations left in the IL between DOM's
jump threading and erroneous path isolation.

In the past we'd been handling this stuff with phi only cprop.  To make
phi only cprop work in this case we'd have to change it to scan
statements within some subset of blocks where it had previously only
scanned PHIs.

I was concerned about the compile-time cost of the additional scanning
plus the extra pass.  So I compared that against using the lattice based
const/copy propagation as well as against the RPO VN bits.

It turns out that the lattice based const/copy propagation does the
least amount of work, closely followed by a limited RPO VN.  The
improved "phi only" copy propagator being the worst.

Given that we can use the lattice copy propagator by just adding the
pass to passes.def whereas using the RPN VN actually requires a little
bit of real code (to set up the entry/exits for the relevant SEME
regions), I went with the lattice copy propagator.

This change adds around .4% instruction executions to my testbed of .i
files.  It has no significant impact on the resulting code -- I see
different register allocation decisions in a lot of places which seem to
primarily result in reversing arguments to comparisons.

FWIW I also considered delaying the erroneous path isolation pass.  I
ultimately decided against that.  My recollection is that its location
came from the desire to clean up those paths early enough in the
pipeline so that other optimizers could do a better job.

We could consider an early/late split here.  Essentially we do the
optimization early, leaving enough data lying around somewhere for a
late pass to look for and issue the warning.  Something like a
__builtin_warning that we leave in the IL, then just before expanding to
RTL, we scan the IL once and issue the __builtin_warnings.

In this specific case the __builtin_warning would be on a path that we
eventually would determine was unreachable at compile time and the path
would be removed.  I suspect we could do something similar for other
warnings coming out of the middle end.

Anyway, this has been bootstrapped and regression tested on x86_64,
ppc64, i686, sparc64, & ppc64le.  It's also been bootstrapped on alpha,
ppc (32 bit), armeb, m68k, riscv64, mipsisa32r4, arm, sh4, & sh4eb.
It's also built and regression tested all the *-elf targets in my tester.

OK for the trunk, or do we want to defer to gcc-10?

Jeff

On Tue, Apr 23, 2019 at 4:29 PM Jeff Law <law@redhat.com> wrote:
>
>
> As discussed in the BZ, this patch addresses the false positive warning
> by cleaning up the const/copy propagations left in the IL between DOM's
> jump threading and erroneous path isolation.
>
> In the past we'd been handling this stuff with phi only cprop.  To make
> phi only cprop work in this case we'd have to change it to scan
> statements within some subset of blocks where it had previously only
> scanned PHIs.
>
> I was concerned about the compile-time cost of the additional scanning
> plus the extra pass.  So I compared that against using the lattice based
> const/copy propagation as well as against the RPO VN bits.
>
> It turns out that the lattice based const/copy propagation does the
> least amount of work, closely followed by a limited RPO VN.  The
> improved "phi only" copy propagator being the worst.

Interesting.

> Given that we can use the lattice copy propagator by just adding the
> pass to passes.def whereas using the RPN VN actually requires a little
> bit of real code (to set up the entry/exits for the relevant SEME
> regions), I went with the lattice copy propagator.
>
> This change adds around .4% instruction executions to my testbed of .i
> files.  It has no significant impact on the resulting code -- I see
> different register allocation decisions in a lot of places which seem to
> primarily result in reversing arguments to comparisons.

Was there a need to have two copy-prop passes in the early
DOM/errorneous-path removal where we previously only had
a single phi-only-prop pass?  Is the testcase fixed also when
doing copy-prop only a single time?

Also the late pass you replace should be right after VRP, not
after warn_restrict (that was a mistake done when adding the
warn_restrict pass).

The main reason I dislike this is that it is an unconditional cleanup
pass run even when we didn't perform any jump threading.  That's
of course the same case as with the existing phi-only-prop passes
but would have been my major argument for the SEME VN
(where at some cut-off of course doing a single whole-function VN
is cheaper than doing N SEME VNs, and I can even think of doing
N SEME regions at once in exchange for doing a whole-function
RPO order compute).

> FWIW I also considered delaying the erroneous path isolation pass.  I
> ultimately decided against that.  My recollection is that its location
> came from the desire to clean up those paths early enough in the
> pipeline so that other optimizers could do a better job.
>
> We could consider an early/late split here.  Essentially we do the
> optimization early, leaving enough data lying around somewhere for a
> late pass to look for and issue the warning.  Something like a
> __builtin_warning that we leave in the IL, then just before expanding to
> RTL, we scan the IL once and issue the __builtin_warnings.
>
> In this specific case the __builtin_warning would be on a path that we
> eventually would determine was unreachable at compile time and the path
> would be removed.  I suspect we could do something similar for other
> warnings coming out of the middle end.
>
> Anyway, this has been bootstrapped and regression tested on x86_64,
> ppc64, i686, sparc64, & ppc64le.  It's also been bootstrapped on alpha,
> ppc (32 bit), armeb, m68k, riscv64, mipsisa32r4, arm, sh4, & sh4eb.
> It's also built and regression tested all the *-elf targets in my tester.
>
> OK for the trunk, or do we want to defer to gcc-10?

I like the pass removal and would say OK if you manage with
a 1:1 replacement (thus get rid of that extra copy-prop between
DOM and pass_isolate_erroneous_paths).

Richard.

>
> Jeff
>
>
>

On 4/24/19 4:44 AM, Richard Biener wrote:
> On Tue, Apr 23, 2019 at 4:29 PM Jeff Law <law@redhat.com> wrote:
>>
>>
>> As discussed in the BZ, this patch addresses the false positive warning
>> by cleaning up the const/copy propagations left in the IL between DOM's
>> jump threading and erroneous path isolation.
>>
>> In the past we'd been handling this stuff with phi only cprop.  To make
>> phi only cprop work in this case we'd have to change it to scan
>> statements within some subset of blocks where it had previously only
>> scanned PHIs.
>>
>> I was concerned about the compile-time cost of the additional scanning
>> plus the extra pass.  So I compared that against using the lattice based
>> const/copy propagation as well as against the RPO VN bits.
>>
>> It turns out that the lattice based const/copy propagation does the
>> least amount of work, closely followed by a limited RPO VN.  The
>> improved "phi only" copy propagator being the worst.
> 
> Interesting.
Definitely.  I didn't dig further than what's mentioned in the BZ.

> 
>> Given that we can use the lattice copy propagator by just adding the
>> pass to passes.def whereas using the RPN VN actually requires a little
>> bit of real code (to set up the entry/exits for the relevant SEME
>> regions), I went with the lattice copy propagator.
>>
>> This change adds around .4% instruction executions to my testbed of .i
>> files.  It has no significant impact on the resulting code -- I see
>> different register allocation decisions in a lot of places which seem to
>> primarily result in reversing arguments to comparisons.
> 
> Was there a need to have two copy-prop passes in the early
> DOM/errorneous-path removal where we previously only had
> a single phi-only-prop pass?  Is the testcase fixed also when
> doing copy-prop only a single time?
The testcase is fixed with a single copyprop (lattice or RPO VN) after
DOM but before erroneous path isolation.   I seriously considered just
dropping the copyprop pass after erroneous path isolation.  I'm pretty
sure it'll regress codegen quality, but it may not be too bad.


> 
> Also the late pass you replace should be right after VRP, not
> after warn_restrict (that was a mistake done when adding the
> warn_restrict pass).
Agreed.  But ISTM we should make that an independent change.

> 
> The main reason I dislike this is that it is an unconditional cleanup
> pass run even when we didn't perform any jump threading.  That's
> of course the same case as with the existing phi-only-prop passes
> but would have been my major argument for the SEME VN
> (where at some cut-off of course doing a single whole-function VN
> is cheaper than doing N SEME VNs, and I can even think of doing
> N SEME regions at once in exchange for doing a whole-function
> RPO order compute).
Yea.  We're certainly doing more work in the cases where we didn't
thread anything.  I've always wanted better ways to indicate what
actions a pass did and using that to bypass subsequent passes if they
weren't going to be profitable.




> 
>> FWIW I also considered delaying the erroneous path isolation pass.  I
>> ultimately decided against that.  My recollection is that its location
>> came from the desire to clean up those paths early enough in the
>> pipeline so that other optimizers could do a better job.
>>
>> We could consider an early/late split here.  Essentially we do the
>> optimization early, leaving enough data lying around somewhere for a
>> late pass to look for and issue the warning.  Something like a
>> __builtin_warning that we leave in the IL, then just before expanding to
>> RTL, we scan the IL once and issue the __builtin_warnings.
>>
>> In this specific case the __builtin_warning would be on a path that we
>> eventually would determine was unreachable at compile time and the path
>> would be removed.  I suspect we could do something similar for other
>> warnings coming out of the middle end.
>>
>> Anyway, this has been bootstrapped and regression tested on x86_64,
>> ppc64, i686, sparc64, & ppc64le.  It's also been bootstrapped on alpha,
>> ppc (32 bit), armeb, m68k, riscv64, mipsisa32r4, arm, sh4, & sh4eb.
>> It's also built and regression tested all the *-elf targets in my tester.
>>
>> OK for the trunk, or do we want to defer to gcc-10?
> 
> I like the pass removal and would say OK if you manage with
> a 1:1 replacement (thus get rid of that extra copy-prop between
> DOM and pass_isolate_erroneous_paths).
That's the one we need to fix the regression.  We might be able to drop
the one after erroneous path isolation which would keep us at the 1:1
replacement.  I'll poke at that.

jeff

On 4/24/19 4:44 AM, Richard Biener wrote:
>> Given that we can use the lattice copy propagator by just adding the
>> pass to passes.def whereas using the RPN VN actually requires a little
>> bit of real code (to set up the entry/exits for the relevant SEME
>> regions), I went with the lattice copy propagator.
>>
>> This change adds around .4% instruction executions to my testbed of .i
>> files.  It has no significant impact on the resulting code -- I see
>> different register allocation decisions in a lot of places which seem to
>> primarily result in reversing arguments to comparisons.
> 
> Was there a need to have two copy-prop passes in the early
> DOM/errorneous-path removal where we previously only had
> a single phi-only-prop pass?  Is the testcase fixed also when
> doing copy-prop only a single time?
So if we replace phi-only cprop with the lattice propagator and move the
pass which currently runs before erroneous path isolation so that it
instead runs before erroneous path isolation we're in pretty good shape.

isolate-2.c and isolate-4.c needed twiddling -- they need to look later
in the pipeline for an expected simplification, but the simplification
still occurs and it's not too much later than before.


I've bootstrapped and regression tested on x86_64, but no other targets
at this point.

OK for the trunk now?


Jeff
* Makefile.in (OBJS): Remove tree-ssa-phionlycprop.c
	* passes.def: Replace all instance of phi-only cprop with the
	lattice propagator.  Move propagation pass from after erroneous
	path isolation to before erroneous path isolation.
	* tree-ssa-phionlycprop.c: Remove.

	* gcc.dg/tree-ssa/20030710-1.c: Update dump file to scan.
	* gcc.dg/isolate-2.c: Likewise.
	* gcc.dg/isolate-4.c: Likewise.
	* gcc.dg/pr19431.c: Accept either ordering of PHI args.



diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index d186d71c91e..5f43d9de00e 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1559,7 +1559,6 @@ OBJS = \
 	tree-ssa-loop.o \
 	tree-ssa-math-opts.o \
 	tree-ssa-operands.o \
-	tree-ssa-phionlycprop.o \
 	tree-ssa-phiopt.o \
 	tree-ssa-phiprop.o \
 	tree-ssa-pre.o \
diff --git a/gcc/passes.def b/gcc/passes.def
index 446a7c48276..bc147c4444d 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -222,19 +222,13 @@ along with GCC; see the file COPYING3.  If not see
 	 trying to move or duplicate pass_dominator somewhere earlier.  */
       NEXT_PASS (pass_thread_jumps);
       NEXT_PASS (pass_dominator, true /* may_peel_loop_headers_p */);
-      /* At this point the majority of const/copy propagations
-	 are exposed.  Go ahead and identify paths that should never
-	 be executed in a conforming program and isolate those paths.
-
-	 This will expose more degenerate PHIs in the main path and
-	 expose more PRE/DOM optimization opportunities.  */
+      /* Threading can leave many const/copy propagations in the IL.
+	 Clean them up.  Failure to do so well can lead to false
+	 positives from warnings for erroneous code.  */
+      NEXT_PASS (pass_copy_prop);
+      /* Identify paths that should never be executed in a conforming
+	 program and isolate those paths.  */
       NEXT_PASS (pass_isolate_erroneous_paths);
-      /* The only const/copy propagation opportunities left after
-	 DOM and erroneous path isolation should be due to degenerate PHI nodes.
-	 So rather than run the full propagators, run a specialized pass which
-	 only examines PHIs to discover const/copy propagation
-	 opportunities.  */
-      NEXT_PASS (pass_phi_only_cprop);
       NEXT_PASS (pass_dse);
       NEXT_PASS (pass_reassoc, true /* insert_powi_p */);
       NEXT_PASS (pass_dce);
@@ -321,13 +315,10 @@ along with GCC; see the file COPYING3.  If not see
       NEXT_PASS (pass_strlen);
       NEXT_PASS (pass_thread_jumps);
       NEXT_PASS (pass_vrp, false /* warn_array_bounds_p */);
-      /* The only const/copy propagation opportunities left after
-	 DOM and VRP should be due to degenerate PHI nodes.  So rather than
-	 run the full propagators, run a specialized pass which
-	 only examines PHIs to discover const/copy propagation
-	 opportunities.  */
       NEXT_PASS (pass_warn_restrict);
-      NEXT_PASS (pass_phi_only_cprop);
+      /* Threading can leave many const/copy propagations in the IL.
+	 Clean them up.  */
+      NEXT_PASS (pass_copy_prop);
       NEXT_PASS (pass_dse);
       NEXT_PASS (pass_cd_dce);
       NEXT_PASS (pass_forwprop);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/20030710-1.c b/gcc/testsuite/gcc.dg/tree-ssa/20030710-1.c
index 3dd3ba8bc17..529c79b26e3 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/20030710-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/20030710-1.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */
-/* { dg-options "-O1 -fdump-tree-phicprop1" } */
+/* { dg-options "-O1 -fdump-tree-copyprop2" } */
 
 extern void abort (void);
 extern void blah (void);
@@ -42,14 +42,14 @@ record_component_aliases (type)
 /* The call to blah should have been eliminated.  If the call is not
    eliminated, then dominator optimizations failed and it'll be
    impossible to delete other unnecessary code.  */
-/* { dg-final { scan-tree-dump-not "blah \\(\\)" "phicprop1" } } */
+/* { dg-final { scan-tree-dump-not "blah \\(\\)" "copyprop2" } } */
   
 /* There should be two IF conditionals.  */
-/* { dg-final { scan-tree-dump-times "if " 2 "phicprop1"} } */
+/* { dg-final { scan-tree-dump-times "if " 2 "copyprop2"} } */
                                                                                 
 /* There should be a single load of type.binfo.  */
-/* { dg-final { scan-tree-dump-times "type\\.binfo" 1 "phicprop1"} } */
+/* { dg-final { scan-tree-dump-times "type\\.binfo" 1 "copyprop2"} } */
 
 /* There should be two loads of vec.length.  */
-/* { dg-final { scan-tree-dump-times "vec.length" 2 "phicprop1"} } */
+/* { dg-final { scan-tree-dump-times "vec.length" 2 "copyprop2"} } */
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/isolate-2.c b/gcc/testsuite/gcc.dg/tree-ssa/isolate-2.c
index b993849e96d..f5cd23ab242 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/isolate-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/isolate-2.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */ 
-/* { dg-options "-O2 -fdelete-null-pointer-checks -fisolate-erroneous-paths-attribute -fdump-tree-isolate-paths -fdump-tree-phicprop1" } */
+/* { dg-options "-O2 -fdelete-null-pointer-checks -fisolate-erroneous-paths-attribute -fdump-tree-isolate-paths -fdump-tree-forwprop3" } */
 /* { dg-skip-if "" keeps_null_pointer_checks } */
 
 
@@ -34,9 +34,9 @@ bar (void)
    a return statement.  We test this twice, once where the NULL flows
    from a PHI, the second with an explicit return 0 in the IL.
 
-   We also verify that after isolation phi-cprop simplifies the
+   We also verify that after isolation cprop simplifies the
    return statement so that it returns &z directly. */
 /* { dg-final { scan-tree-dump-times "__builtin_trap" 2 "isolate-paths"} } */
-/* { dg-final { scan-tree-dump-times "return &z;" 1 "phicprop1"} } */
+/* { dg-final { scan-tree-dump-times "return &z;" 1 "forwprop3"} } */
 
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/isolate-4.c b/gcc/testsuite/gcc.dg/tree-ssa/isolate-4.c
index 0a88d7d47f6..f357e16d3d7 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/isolate-4.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/isolate-4.c
@@ -1,5 +1,5 @@
 /* { dg-do compile } */ 
-/* { dg-options "-O2 -fdelete-null-pointer-checks -fisolate-erroneous-paths-attribute -fdump-tree-isolate-paths -fdump-tree-phicprop1" } */
+/* { dg-options "-O2 -fdelete-null-pointer-checks -fisolate-erroneous-paths-attribute -fdump-tree-isolate-paths -fdump-tree-ccp3" } */
 /* { dg-skip-if "" keeps_null_pointer_checks } */
 
 
@@ -26,6 +26,6 @@ bar (void)
    We also verify that after isolation phi-cprop simplifies the
    return statement so that it returns &z directly. */
 /* { dg-final { scan-tree-dump-times "__builtin_trap" 2 "isolate-paths"} } */
-/* { dg-final { scan-tree-dump-times "foo .&z.;" 1 "phicprop1"} } */
+/* { dg-final { scan-tree-dump-times "foo .&z.;" 1 "ccp3"} } */
 
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr19431.c b/gcc/testsuite/gcc.dg/tree-ssa/pr19431.c
index 2f656ceccbc..a1f46c7aec5 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr19431.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr19431.c
@@ -24,4 +24,4 @@ int f(int k, int i1, int j1)
   return *f1;
 }
 
-/* { dg-final { scan-tree-dump "\[^\r\n\]*_. = PHI <i1_\[^,\]*, j1_\[^>\]*>" "optimized" } } */
+/* { dg-final { scan-tree-dump "\[^\r\n\]*_. = PHI <\[ij\]1_\[^,\]*, \[ij\]1_\[^>\]*>" "optimized" } } */
diff --git a/gcc/tree-ssa-phionlycprop.c b/gcc/tree-ssa-phionlycprop.c
deleted file mode 100644
index f367800da41..00000000000
--- a/gcc/tree-ssa-phionlycprop.c
+++ /dev/null
@@ -1,580 +0,0 @@
-/* Const/Copy propagation originating from degenerate PHIs
-   Copyright (C) 2001-2019 Free Software Foundation, Inc.
-
-This file is part of GCC.
-
-GCC is free software; you can redistribute it and/or modify
-it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 3, or (at your option)
-any later version.
-
-GCC is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-GNU General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING3.  If not see
-<http://www.gnu.org/licenses/>.  */
-
-#include "config.h"
-#include "system.h"
-#include "coretypes.h"
-#include "backend.h"
-#include "cfghooks.h"
-#include "tree.h"
-#include "gimple.h"
-#include "ssa.h"
-#include "fold-const.h"
-#include "cfgloop.h"
-#include "gimple-pretty-print.h"
-#include "gimple-fold.h"
-#include "tree-eh.h"
-#include "gimple-iterator.h"
-#include "tree-cfg.h"
-#include "tree-pass.h"
-#include "tree-ssa-propagate.h"
-
-
-/* PHI-ONLY copy and constant propagation.  This pass is meant to clean
-   up degenerate PHIs created by or exposed by jump threading.  */
-
-/* Given a statement STMT, which is either a PHI node or an assignment,
-   remove it from the IL.  */
-
-static void
-remove_stmt_or_phi (gimple *stmt)
-{
-  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
-
-  if (gimple_code (stmt) == GIMPLE_PHI)
-    remove_phi_node (&gsi, true);
-  else
-    {
-      gsi_remove (&gsi, true);
-      release_defs (stmt);
-    }
-}
-
-/* Given a statement STMT, which is either a PHI node or an assignment,
-   return the "rhs" of the node, in the case of a non-degenerate
-   phi, NULL is returned.  */
-
-static tree
-get_rhs_or_phi_arg (gimple *stmt)
-{
-  if (gimple_code (stmt) == GIMPLE_PHI)
-    return degenerate_phi_result (as_a <gphi *> (stmt));
-  else if (gimple_assign_single_p (stmt))
-    return gimple_assign_rhs1 (stmt);
-  else
-    gcc_unreachable ();
-}
-
-
-/* Given a statement STMT, which is either a PHI node or an assignment,
-   return the "lhs" of the node.  */
-
-static tree
-get_lhs_or_phi_result (gimple *stmt)
-{
-  if (gimple_code (stmt) == GIMPLE_PHI)
-    return gimple_phi_result (stmt);
-  else if (is_gimple_assign (stmt))
-    return gimple_assign_lhs (stmt);
-  else
-    gcc_unreachable ();
-}
-
-/* Propagate RHS into all uses of LHS (when possible).
-
-   RHS and LHS are derived from STMT, which is passed in solely so
-   that we can remove it if propagation is successful.
-
-   When propagating into a PHI node or into a statement which turns
-   into a trivial copy or constant initialization, set the
-   appropriate bit in INTERESTING_NAMEs so that we will visit those
-   nodes as well in an effort to pick up secondary optimization
-   opportunities. 
-
-   NEED_EH_CLEANUP tracks blocks that need their EH information
-   cleaned up after changing EH information on a statement.  */
-
-static bool
-propagate_rhs_into_lhs (gimple *stmt, tree lhs, tree rhs,
-			bitmap interesting_names, bitmap need_eh_cleanup)
-{
-  bool cfg_altered = false;
-
-  /* First verify that propagation is valid.  */
-  if (may_propagate_copy (lhs, rhs))
-    {
-      use_operand_p use_p;
-      imm_use_iterator iter;
-      gimple *use_stmt;
-      bool all = true;
-
-      /* Dump details.  */
-      if (dump_file && (dump_flags & TDF_DETAILS))
-	{
-	  fprintf (dump_file, "  Replacing '");
-	  print_generic_expr (dump_file, lhs, dump_flags);
-	  fprintf (dump_file, "' with %s '",
-	           (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
-		   print_generic_expr (dump_file, rhs, dump_flags);
-	  fprintf (dump_file, "'\n");
-	}
-
-      /* Walk over every use of LHS and try to replace the use with RHS.
-	 At this point the only reason why such a propagation would not
-	 be successful would be if the use occurs in an ASM_EXPR.  */
-      FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
-	{
-	  /* Leave debug stmts alone.  If we succeed in propagating
-	     all non-debug uses, we'll drop the DEF, and propagation
-	     into debug stmts will occur then.  */
-	  if (gimple_debug_bind_p (use_stmt))
-	    continue;
-
-	  /* It's not always safe to propagate into an ASM_EXPR.  */
-	  if (gimple_code (use_stmt) == GIMPLE_ASM
-              && ! may_propagate_copy_into_asm (lhs))
-	    {
-	      all = false;
-	      continue;
-	    }
-
-	  /* It's not ok to propagate into the definition stmt of RHS.
-		<bb 9>:
-		  # prephitmp.12_36 = PHI <g_67.1_6(9)>
-		  g_67.1_6 = prephitmp.12_36;
-		  goto <bb 9>;
-	     While this is strictly all dead code we do not want to
-	     deal with this here.  */
-	  if (TREE_CODE (rhs) == SSA_NAME
-	      && SSA_NAME_DEF_STMT (rhs) == use_stmt)
-	    {
-	      all = false;
-	      continue;
-	    }
-
-	  /* Dump details.  */
-	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    {
-	      fprintf (dump_file, "    Original statement:");
-	      print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
-	    }
-
-	  /* Propagate the RHS into this use of the LHS.  */
-	  FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
-	    propagate_value (use_p, rhs);
-
-	  /* Special cases to avoid useless calls into the folding
-	     routines, operand scanning, etc.
-
-	     Propagation into a PHI may cause the PHI to become
-	     a degenerate, so mark the PHI as interesting.  No other
-	     actions are necessary.  */
-	  if (gimple_code (use_stmt) == GIMPLE_PHI)
-	    {
-	      tree result;
-
-	      /* Dump details.  */
-	      if (dump_file && (dump_flags & TDF_DETAILS))
-		{
-		  fprintf (dump_file, "    Updated statement:");
-		  print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
-		}
-
-	      result = get_lhs_or_phi_result (use_stmt);
-	      bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
-	      continue;
-	    }
-
-	  /* From this point onward we are propagating into a
-	     real statement.  Folding may (or may not) be possible,
-	     we may expose new operands, expose dead EH edges,
-	     etc.  */
-          /* NOTE tuples. In the tuples world, fold_stmt_inplace
-             cannot fold a call that simplifies to a constant,
-             because the GIMPLE_CALL must be replaced by a
-             GIMPLE_ASSIGN, and there is no way to effect such a
-             transformation in-place.  We might want to consider
-             using the more general fold_stmt here.  */
-	    {
-	      gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
-	      fold_stmt_inplace (&gsi);
-	    }
-
-	  /* Sometimes propagation can expose new operands to the
-	     renamer.  */
-	  update_stmt (use_stmt);
-
-	  /* Dump details.  */
-	  if (dump_file && (dump_flags & TDF_DETAILS))
-	    {
-	      fprintf (dump_file, "    Updated statement:");
-	      print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
-	    }
-
-	  /* If we replaced a variable index with a constant, then
-	     we would need to update the invariant flag for ADDR_EXPRs.  */
-          if (gimple_assign_single_p (use_stmt)
-              && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
-	    recompute_tree_invariant_for_addr_expr
-                (gimple_assign_rhs1 (use_stmt));
-
-	  /* If we cleaned up EH information from the statement,
-	     mark its containing block as needing EH cleanups.  */
-	  if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
-	    {
-	      bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
-	      if (dump_file && (dump_flags & TDF_DETAILS))
-		fprintf (dump_file, "  Flagged to clear EH edges.\n");
-	    }
-
-	  /* Propagation may expose new trivial copy/constant propagation
-	     opportunities.  */
-          if (gimple_assign_single_p (use_stmt)
-              && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
-              && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
-                  || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
-            {
-	      tree result = get_lhs_or_phi_result (use_stmt);
-	      bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
-	    }
-
-	  /* Propagation into these nodes may make certain edges in
-	     the CFG unexecutable.  We want to identify them as PHI nodes
-	     at the destination of those unexecutable edges may become
-	     degenerates.  */
-	  else if (gimple_code (use_stmt) == GIMPLE_COND
-		   || gimple_code (use_stmt) == GIMPLE_SWITCH
-		   || gimple_code (use_stmt) == GIMPLE_GOTO)
-            {
-	      tree val;
-
-	      if (gimple_code (use_stmt) == GIMPLE_COND)
-                val = fold_binary_loc (gimple_location (use_stmt),
-				   gimple_cond_code (use_stmt),
-                                   boolean_type_node,
-                                   gimple_cond_lhs (use_stmt),
-                                   gimple_cond_rhs (use_stmt));
-              else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
-		val = gimple_switch_index (as_a <gswitch *> (use_stmt));
-	      else
-		val = gimple_goto_dest  (use_stmt);
-
-	      if (val && is_gimple_min_invariant (val))
-		{
-		  basic_block bb = gimple_bb (use_stmt);
-		  edge te = find_taken_edge (bb, val);
-		  if (!te)
-		    continue;
-
-		  edge_iterator ei;
-		  edge e;
-		  gimple_stmt_iterator gsi;
-		  gphi_iterator psi;
-
-		  /* Remove all outgoing edges except TE.  */
-		  for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
-		    {
-		      if (e != te)
-			{
-			  /* Mark all the PHI nodes at the destination of
-			     the unexecutable edge as interesting.  */
-                          for (psi = gsi_start_phis (e->dest);
-                               !gsi_end_p (psi);
-                               gsi_next (&psi))
-                            {
-                              gphi *phi = psi.phi ();
-
-			      tree result = gimple_phi_result (phi);
-			      int version = SSA_NAME_VERSION (result);
-
-			      bitmap_set_bit (interesting_names, version);
-			    }
-
-			  te->probability += e->probability;
-
-			  remove_edge (e);
-			  cfg_altered = true;
-			}
-		      else
-			ei_next (&ei);
-		    }
-
-		  gsi = gsi_last_bb (gimple_bb (use_stmt));
-		  gsi_remove (&gsi, true);
-
-		  /* And fixup the flags on the single remaining edge.  */
-		  te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
-		  te->flags &= ~EDGE_ABNORMAL;
-		  te->flags |= EDGE_FALLTHRU;
-	        }
-	    }
-	}
-
-      /* Ensure there is nothing else to do. */
-      gcc_assert (!all || has_zero_uses (lhs));
-
-      /* If we were able to propagate away all uses of LHS, then
-	 we can remove STMT.  */
-      if (all)
-	remove_stmt_or_phi (stmt);
-    }
-  return cfg_altered;
-}
-
-/* STMT is either a PHI node (potentially a degenerate PHI node) or
-   a statement that is a trivial copy or constant initialization.
-
-   Attempt to eliminate STMT by propagating its RHS into all uses of
-   its LHS.  This may in turn set new bits in INTERESTING_NAMES
-   for nodes we want to revisit later.
-
-   All exit paths should clear INTERESTING_NAMES for the result
-   of STMT.
-
-   NEED_EH_CLEANUP tracks blocks that need their EH information
-   cleaned up after changing EH information on a statement.  It is
-   not set or queried here, but passed along to children.  */
-
-static bool
-eliminate_const_or_copy (gimple *stmt, bitmap interesting_names,
-			 bitmap need_eh_cleanup)
-{
-  tree lhs = get_lhs_or_phi_result (stmt);
-  tree rhs;
-  int version = SSA_NAME_VERSION (lhs);
-  bool cfg_altered = false;
-
-  /* If the LHS of this statement or PHI has no uses, then we can
-     just eliminate it.  This can occur if, for example, the PHI
-     was created by block duplication due to threading and its only
-     use was in the conditional at the end of the block which was
-     deleted.  */
-  if (has_zero_uses (lhs))
-    {
-      bitmap_clear_bit (interesting_names, version);
-      remove_stmt_or_phi (stmt);
-      return cfg_altered;
-    }
-
-  /* Get the RHS of the assignment or PHI node if the PHI is a
-     degenerate.  */
-  rhs = get_rhs_or_phi_arg (stmt);
-  if (!rhs)
-    {
-      bitmap_clear_bit (interesting_names, version);
-      return cfg_altered;
-    }
-
-  if (!virtual_operand_p (lhs))
-    cfg_altered = propagate_rhs_into_lhs (stmt, lhs, rhs,
-					  interesting_names, need_eh_cleanup);
-  else
-    {
-      gimple *use_stmt;
-      imm_use_iterator iter;
-      use_operand_p use_p;
-      /* For virtual operands we have to propagate into all uses as
-         otherwise we will create overlapping life-ranges.  */
-      FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
-	FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
-	  SET_USE (use_p, rhs);
-      if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
-	SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
-      remove_stmt_or_phi (stmt);
-    }
-
-  /* Note that STMT may well have been deleted by now, so do
-     not access it, instead use the saved version # to clear
-     T's entry in the worklist.  */
-  bitmap_clear_bit (interesting_names, version);
-  return cfg_altered;
-}
-
-/* The first phase in degenerate PHI elimination.
-
-   Eliminate the degenerate PHIs in BB, then recurse on the
-   dominator children of BB. 
-
-   INTERESTING_NAMES tracks SSA_NAMEs that we may want to revisit
-   in the future.  It is not set or queried here, but passed along
-   to children. 
-
-   NEED_EH_CLEANUP tracks blocks that need their EH information
-   cleaned up after changing EH information on a statement.  It is
-   not set or queried here, but passed along to children.  */
-
-static bool
-eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names,
-			     bitmap need_eh_cleanup)
-{
-  gphi_iterator gsi;
-  basic_block son;
-  bool cfg_altered = false;
-
-  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
-    {
-      gphi *phi = gsi.phi ();
-      /* We might end up removing PHI so advance the iterator now.  */
-      gsi_next (&gsi);
-      cfg_altered |= eliminate_const_or_copy (phi, interesting_names,
-					      need_eh_cleanup);
-    }
-
-  /* Recurse into the dominator children of BB.  */
-  for (son = first_dom_son (CDI_DOMINATORS, bb);
-       son;
-       son = next_dom_son (CDI_DOMINATORS, son))
-    cfg_altered |= eliminate_degenerate_phis_1 (son, interesting_names,
-						need_eh_cleanup);
-
-  return cfg_altered;
-}
-
-
-/* A very simple pass to eliminate degenerate PHI nodes from the
-   IL.  This is meant to be fast enough to be able to be run several
-   times in the optimization pipeline.
-
-   Certain optimizations, particularly those which duplicate blocks
-   or remove edges from the CFG can create or expose PHIs which are
-   trivial copies or constant initializations.
-
-   While we could pick up these optimizations in DOM or with the
-   combination of copy-prop and CCP, those solutions are far too
-   heavy-weight for our needs.
-
-   This implementation has two phases so that we can efficiently
-   eliminate the first order degenerate PHIs and second order
-   degenerate PHIs.
-
-   The first phase performs a dominator walk to identify and eliminate
-   the vast majority of the degenerate PHIs.  When a degenerate PHI
-   is identified and eliminated any affected statements or PHIs
-   are put on a worklist.
-
-   The second phase eliminates degenerate PHIs and trivial copies
-   or constant initializations using the worklist.  This is how we
-   pick up the secondary optimization opportunities with minimal
-   cost.  */
-
-namespace {
-
-const pass_data pass_data_phi_only_cprop =
-{
-  GIMPLE_PASS, /* type */
-  "phicprop", /* name */
-  OPTGROUP_NONE, /* optinfo_flags */
-  TV_TREE_PHI_CPROP, /* tv_id */
-  ( PROP_cfg | PROP_ssa ), /* properties_required */
-  0, /* properties_provided */
-  0, /* properties_destroyed */
-  0, /* todo_flags_start */
-  ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
-};
-
-class pass_phi_only_cprop : public gimple_opt_pass
-{
-public:
-  pass_phi_only_cprop (gcc::context *ctxt)
-    : gimple_opt_pass (pass_data_phi_only_cprop, ctxt)
-  {}
-
-  /* opt_pass methods: */
-  opt_pass * clone () { return new pass_phi_only_cprop (m_ctxt); }
-  virtual bool gate (function *) { return flag_tree_dom != 0; }
-  virtual unsigned int execute (function *);
-
-}; // class pass_phi_only_cprop
-
-unsigned int
-pass_phi_only_cprop::execute (function *fun)
-{
-  bool cfg_altered = false;
-
-  /* Bitmap of blocks which need EH information updated.  We cannot
-     update it on-the-fly as doing so invalidates the dominator tree.  */
-  auto_bitmap need_eh_cleanup;
-
-  /* INTERESTING_NAMES is effectively our worklist, indexed by
-     SSA_NAME_VERSION.
-
-     A set bit indicates that the statement or PHI node which
-     defines the SSA_NAME should be (re)examined to determine if
-     it has become a degenerate PHI or trivial const/copy propagation
-     opportunity.
-
-     Experiments have show we generally get better compilation
-     time behavior with bitmaps rather than sbitmaps.  */
-  auto_bitmap interesting_names;
-  auto_bitmap interesting_names1;
-
-  calculate_dominance_info (CDI_DOMINATORS);
-  cfg_altered = false;
-
-  /* First phase.  Eliminate degenerate PHIs via a dominator
-     walk of the CFG.
-
-     Experiments have indicated that we generally get better
-     compile-time behavior by visiting blocks in the first
-     phase in dominator order.  Presumably this is because walking
-     in dominator order leaves fewer PHIs for later examination
-     by the worklist phase.  */
-  cfg_altered = eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR_FOR_FN (fun),
-					     interesting_names,
-					     need_eh_cleanup);
-
-  /* Second phase.  Eliminate second order degenerate PHIs as well
-     as trivial copies or constant initializations identified by
-     the first phase or this phase.  Basically we keep iterating
-     until our set of INTERESTING_NAMEs is empty.   */
-  while (!bitmap_empty_p (interesting_names))
-    {
-      unsigned int i;
-      bitmap_iterator bi;
-
-      /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
-	 changed during the loop.  Copy it to another bitmap and
-	 use that.  */
-      bitmap_copy (interesting_names1, interesting_names);
-
-      EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
-	{
-	  tree name = ssa_name (i);
-
-	  /* Ignore SSA_NAMEs that have been released because
-	     their defining statement was deleted (unreachable).  */
-	  if (name)
-	    cfg_altered
-	      |= eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
-					  interesting_names, need_eh_cleanup);
-	}
-    }
-
-  if (cfg_altered)
-    {
-      free_dominance_info (CDI_DOMINATORS);
-      /* If we changed the CFG schedule loops for fixup by cfgcleanup.  */
-      loops_state_set (LOOPS_NEED_FIXUP);
-    }
-
-  /* Propagation of const and copies may make some EH edges dead.  Purge
-     such edges from the CFG as needed.  */
-  if (!bitmap_empty_p (need_eh_cleanup))
-    gimple_purge_all_dead_eh_edges (need_eh_cleanup);
-
-  return 0;
-}
-
-} // anon namespace
-
-gimple_opt_pass *
-make_pass_phi_only_cprop (gcc::context *ctxt)
-{
-  return new pass_phi_only_cprop (ctxt);
-}

On April 24, 2019 8:31:44 PM GMT+02:00, Jeff Law <law@redhat.com> wrote:
>On 4/24/19 4:44 AM, Richard Biener wrote:
>> On Tue, Apr 23, 2019 at 4:29 PM Jeff Law <law@redhat.com> wrote:
>>>
>>>
>>> As discussed in the BZ, this patch addresses the false positive
>warning
>>> by cleaning up the const/copy propagations left in the IL between
>DOM's
>>> jump threading and erroneous path isolation.
>>>
>>> In the past we'd been handling this stuff with phi only cprop.  To
>make
>>> phi only cprop work in this case we'd have to change it to scan
>>> statements within some subset of blocks where it had previously only
>>> scanned PHIs.
>>>
>>> I was concerned about the compile-time cost of the additional
>scanning
>>> plus the extra pass.  So I compared that against using the lattice
>based
>>> const/copy propagation as well as against the RPO VN bits.
>>>
>>> It turns out that the lattice based const/copy propagation does the
>>> least amount of work, closely followed by a limited RPO VN.  The
>>> improved "phi only" copy propagator being the worst.
>> 
>> Interesting.
>Definitely.  I didn't dig further than what's mentioned in the BZ.
>
>> 
>>> Given that we can use the lattice copy propagator by just adding the
>>> pass to passes.def whereas using the RPN VN actually requires a
>little
>>> bit of real code (to set up the entry/exits for the relevant SEME
>>> regions), I went with the lattice copy propagator.
>>>
>>> This change adds around .4% instruction executions to my testbed of
>.i
>>> files.  It has no significant impact on the resulting code -- I see
>>> different register allocation decisions in a lot of places which
>seem to
>>> primarily result in reversing arguments to comparisons.
>> 
>> Was there a need to have two copy-prop passes in the early
>> DOM/errorneous-path removal where we previously only had
>> a single phi-only-prop pass?  Is the testcase fixed also when
>> doing copy-prop only a single time?
>The testcase is fixed with a single copyprop (lattice or RPO VN) after
>DOM but before erroneous path isolation.   I seriously considered just
>dropping the copyprop pass after erroneous path isolation.  I'm pretty
>sure it'll regress codegen quality, but it may not be too bad.
>
>
>> 
>> Also the late pass you replace should be right after VRP, not
>> after warn_restrict (that was a mistake done when adding the
>> warn_restrict pass).
>Agreed.  But ISTM we should make that an independent change.
>
>> 
>> The main reason I dislike this is that it is an unconditional cleanup
>> pass run even when we didn't perform any jump threading.  That's
>> of course the same case as with the existing phi-only-prop passes
>> but would have been my major argument for the SEME VN
>> (where at some cut-off of course doing a single whole-function VN
>> is cheaper than doing N SEME VNs, and I can even think of doing
>> N SEME regions at once in exchange for doing a whole-function
>> RPO order compute).
>Yea.  We're certainly doing more work in the cases where we didn't
>thread anything.  I've always wanted better ways to indicate what
>actions a pass did and using that to bypass subsequent passes if they
>weren't going to be profitable.
>
>
>
>
>> 
>>> FWIW I also considered delaying the erroneous path isolation pass. 
>I
>>> ultimately decided against that.  My recollection is that its
>location
>>> came from the desire to clean up those paths early enough in the
>>> pipeline so that other optimizers could do a better job.
>>>
>>> We could consider an early/late split here.  Essentially we do the
>>> optimization early, leaving enough data lying around somewhere for a
>>> late pass to look for and issue the warning.  Something like a
>>> __builtin_warning that we leave in the IL, then just before
>expanding to
>>> RTL, we scan the IL once and issue the __builtin_warnings.
>>>
>>> In this specific case the __builtin_warning would be on a path that
>we
>>> eventually would determine was unreachable at compile time and the
>path
>>> would be removed.  I suspect we could do something similar for other
>>> warnings coming out of the middle end.
>>>
>>> Anyway, this has been bootstrapped and regression tested on x86_64,
>>> ppc64, i686, sparc64, & ppc64le.  It's also been bootstrapped on
>alpha,
>>> ppc (32 bit), armeb, m68k, riscv64, mipsisa32r4, arm, sh4, & sh4eb.
>>> It's also built and regression tested all the *-elf targets in my
>tester.
>>>
>>> OK for the trunk, or do we want to defer to gcc-10?
>> 
>> I like the pass removal and would say OK if you manage with
>> a 1:1 replacement (thus get rid of that extra copy-prop between
>> DOM and pass_isolate_erroneous_paths).
>That's the one we need to fix the regression.  We might be able to drop
>the one after erroneous path isolation which would keep us at the 1:1
>replacement.  I'll poke at that.

Works for me as well if testing succeeds. 

Richard. 

>jeff

On April 24, 2019 11:26:28 PM GMT+02:00, Jeff Law <law@redhat.com> wrote:
>On 4/24/19 4:44 AM, Richard Biener wrote:
>>> Given that we can use the lattice copy propagator by just adding the
>>> pass to passes.def whereas using the RPN VN actually requires a
>little
>>> bit of real code (to set up the entry/exits for the relevant SEME
>>> regions), I went with the lattice copy propagator.
>>>
>>> This change adds around .4% instruction executions to my testbed of
>.i
>>> files.  It has no significant impact on the resulting code -- I see
>>> different register allocation decisions in a lot of places which
>seem to
>>> primarily result in reversing arguments to comparisons.
>> 
>> Was there a need to have two copy-prop passes in the early
>> DOM/errorneous-path removal where we previously only had
>> a single phi-only-prop pass?  Is the testcase fixed also when
>> doing copy-prop only a single time?
>So if we replace phi-only cprop with the lattice propagator and move
>the
>pass which currently runs before erroneous path isolation so that it
>instead runs before erroneous path isolation we're in pretty good
>shape.
>
>isolate-2.c and isolate-4.c needed twiddling -- they need to look later
>in the pipeline for an expected simplification, but the simplification
>still occurs and it's not too much later than before.
>
>
>I've bootstrapped and regression tested on x86_64, but no other targets
>at this point.
>
>OK for the trunk now?

OK. 

Richard. 

>
>Jeff