Add a pass to back-propagate use information

This patch adds a pass that collects information that is common to
all uses of an SSA name X and back-propagates that information up
the statements that generate X.  The general idea is to use the
information to simplify instructions (rather than a pure DCE) so
I've simply called it gimple-ssa-backprop.c, to go with
tree-ssa-forwprop.c.

At the moment the only use of the pass is to remove unnecessary
sign operations, so that it's effectively a global version of
fold_strip_sign_ops.  I'm hoping it could be extended in future
to record which bits of an integer are significant.  There are
probably other potential uses too.

A later patch gets rid of fold_strip_sign_ops.

Tested on x86_64-linux-gnu, aarch64-linux-gnu and arm-linux-gnueabi.

gcc/
	* doc/invoke.texi (-fdump-tree-backprop, -fssa-backprop): Document.
	* Makefile.in (OBJS): Add gimple-ssa-backprop.o.
	* common.opt (fssa-backprop): New option.
	* fold-const.h (negate_mathfn_p): Declare.
	* fold-const.c (negate_mathfn_p): Make public.
	* timevar.def (TV_TREE_BACKPROP): New.
	* tree-pass.h (make_pass_backprop): Declare.
	* passes.def (pass_backprop): Add.
	* gimple-ssa-backprop.c: New file.

gcc/testsuite/
	* gcc.dg/tree-ssa/backprop-1.c, gcc.dg/tree-ssa/backprop-2.c,
	gcc.dg/tree-ssa/backprop-3.c, gcc.dg/tree-ssa/backprop-4.c,
	gcc.dg/tree-ssa/backprop-5.c, gcc.dg/tree-ssa/backprop-6.c: New tests.

From-SVN: r229139

1 files changed, 19 insertions, 4 deletions

diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 027ce96..cd82544 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -343,6 +343,7 @@ Objective-C and Objective-C++ Dialects}.
 -fdump-tree-dse@r{[}-@var{n}@r{]} @gol
 -fdump-tree-phiprop@r{[}-@var{n}@r{]} @gol
 -fdump-tree-phiopt@r{[}-@var{n}@r{]} @gol
+-fdump-tree-backprop@r{[}-@var{n}@r{]} @gol
 -fdump-tree-forwprop@r{[}-@var{n}@r{]} @gol
 -fdump-tree-nrv -fdump-tree-vect @gol
 -fdump-tree-sink @gol
@@ -443,9 +444,9 @@ Objective-C and Objective-C++ Dialects}.
 -fschedule-insns -fschedule-insns2 -fsection-anchors @gol
 -fselective-scheduling -fselective-scheduling2 @gol
 -fsel-sched-pipelining -fsel-sched-pipelining-outer-loops @gol
--fsemantic-interposition @gol
--fshrink-wrap -fsignaling-nans -fsingle-precision-constant @gol
--fsplit-ivs-in-unroller -fsplit-wide-types -fssa-phiopt @gol
+-fsemantic-interposition -fshrink-wrap -fsignaling-nans @gol
+-fsingle-precision-constant -fsplit-ivs-in-unroller @gol
+-fsplit-wide-types -fssa-backprop -fssa-phiopt @gol
 -fstack-protector -fstack-protector-all -fstack-protector-strong @gol
 -fstack-protector-explicit -fstdarg-opt -fstrict-aliasing @gol
 -fstrict-overflow -fthread-jumps -ftracer -ftree-bit-ccp @gol
@@ -7236,6 +7237,12 @@ name is made by appending @file{.dse} to the source file name.
 Dump each function after optimizing PHI nodes into straightline code.  The file
 name is made by appending @file{.phiopt} to the source file name.
 
+@item backprop
+@opindex fdump-tree-backprop
+Dump each function after back-propagating use information up the definition
+chain.  The file name is made by appending @file{.backprop} to the
+source file name.
+
 @item forwprop
 @opindex fdump-tree-forwprop
 Dump each function after forward propagating single use variables.  The file
@@ -7707,9 +7714,10 @@ compilation time.
 -freorder-blocks @gol
 -fshrink-wrap @gol
 -fsplit-wide-types @gol
+-fssa-backprop @gol
+-fssa-phiopt @gol
 -ftree-bit-ccp @gol
 -ftree-ccp @gol
--fssa-phiopt @gol
 -ftree-ch @gol
 -ftree-coalesce-vars @gol
 -ftree-copy-prop @gol
@@ -8795,6 +8803,13 @@ Perform sparse conditional constant propagation (CCP) on trees.  This
 pass only operates on local scalar variables and is enabled by default
 at @option{-O} and higher.
 
+@item -fssa-backprop
+@opindex fssa-backprop
+Propagate information about uses of a value up the definition chain
+in order to simplify the definitions.  For example, this pass strips
+sign operations if the sign of a value never matters.  The flag is
+enabled by default at @option{-O} and higher.
+
 @item -fssa-phiopt
 @opindex fssa-phiopt
 Perform pattern matching on SSA PHI nodes to optimize conditional