From patchwork Thu Oct 15 13:17:05 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Sandiford X-Patchwork-Id: 530697 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id AD9EC1402BF for ; Fri, 16 Oct 2015 00:17:28 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=BEb8jWLt; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type :content-transfer-encoding; q=dns; s=default; b=xZS8cy4BfSMtMumT 5Lz+a/LRSNIX0FPfNnf09cboQlMvAlEyPrhLgBih6J8piFKQe8sCuciXjGN42ZoB Stjs4FwmB3lgUb4PyTig2RM9ih+GXU6DUDKWU+o3vH7ZjIiwGASg7fwHbNtUYL4G dksg9kFUYrlx1bA+eVrilfsuJtQ= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:subject:date:message-id:mime-version:content-type :content-transfer-encoding; s=default; bh=vacFVVexVm/7oAg1E1hqvo +I0nU=; b=BEb8jWLtrAbQlaWoch7IyGsQubsz4UujDOBefHUz6ekD41ioDA2EAB zQUz1ff/ZjSZHJmOuGeqVBSAGqOsD+Ec1RvRBVqhXvgUTgmeJ0Ay9y6oHebpHeY/ kcVyQlnadCTTuFqEVH7IeQ77/GXFv+YmUF+QsOuX0B7ItyIbwNtJA= Received: (qmail 109186 invoked by alias); 15 Oct 2015 13:17:17 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 109169 invoked by uid 89); 15 Oct 2015 13:17:17 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-0.1 required=5.0 tests=AWL, BAYES_50, SPF_PASS autolearn=ham version=3.3.2 X-HELO: eu-smtp-delivery-143.mimecast.com Received: from eu-smtp-delivery-143.mimecast.com (HELO eu-smtp-delivery-143.mimecast.com) (146.101.78.143) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Thu, 15 Oct 2015 13:17:10 +0000 Received: from cam-owa1.Emea.Arm.com (fw-tnat.cambridge.arm.com [217.140.96.140]) by eu-smtp-1.mimecast.com with ESMTP id uk-mta-5-zz2DaGe6Ra-c7dG0ioavEw-1; Thu, 15 Oct 2015 14:17:05 +0100 Received: from localhost ([10.1.2.79]) by cam-owa1.Emea.Arm.com with Microsoft SMTPSVC(6.0.3790.3959); Thu, 15 Oct 2015 14:17:05 +0100 From: Richard Sandiford To: gcc-patches@gcc.gnu.org Mail-Followup-To: gcc-patches@gcc.gnu.org, richard.sandiford@arm.com Subject: Add a pass to back-propagate use information Date: Thu, 15 Oct 2015 14:17:05 +0100 Message-ID: <87pp0gi84u.fsf@e105548-lin.cambridge.arm.com> User-Agent: Gnus/5.130012 (Ma Gnus v0.12) Emacs/24.3 (gnu/linux) MIME-Version: 1.0 X-MC-Unique: zz2DaGe6Ra-c7dG0ioavEw-1 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 tree-ssa-backprop.c, to go with tree-ssa-forwprop.c. At the moment the only use of the pass is to remove unnecessry 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. OK to install? Thanks, Richard gcc/ * doc/invoke.texi (-fdump-tree-backprop, -ftree-backprop): Document. * Makefile.in (OBJS): Add tree-ssa-backprop.o. * common.opt (ftree-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-passes.h (make_pass_backprop): Declare. * passes.def (pass_backprop): Add. * tree-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. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 783e4c9..69e669d 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1445,6 +1445,7 @@ OBJS = \ tree-switch-conversion.o \ tree-ssa-address.o \ tree-ssa-alias.o \ + tree-ssa-backprop.o \ tree-ssa-ccp.o \ tree-ssa-coalesce.o \ tree-ssa-copy.o \ diff --git a/gcc/common.opt b/gcc/common.opt index 5060208..5aef625 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -2364,6 +2364,10 @@ ftree-pta Common Report Var(flag_tree_pta) Optimization Perform function-local points-to analysis on trees. +ftree-backprop +Common Report Var(flag_tree_backprop) Init(1) Optimization +Enable backward propagation of use properties at the tree level. + ftree-reassoc Common Report Var(flag_tree_reassoc) Init(1) Optimization Enable reassociation on tree level diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 54e9f12..fe15d08 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 @@ -451,8 +452,8 @@ Objective-C and Objective-C++ Dialects}. -fstrict-overflow -fthread-jumps -ftracer -ftree-bit-ccp @gol -ftree-builtin-call-dce -ftree-ccp -ftree-ch @gol -ftree-coalesce-vars -ftree-copy-prop -ftree-dce -ftree-dominator-opts @gol --ftree-dse -ftree-forwprop -ftree-fre -ftree-loop-if-convert @gol --ftree-loop-if-convert-stores -ftree-loop-im @gol +-ftree-dse -ftree-backprop -ftree-forwprop -ftree-fre @gol +-ftree-loop-if-convert -ftree-loop-if-convert-stores -ftree-loop-im @gol -ftree-phiprop -ftree-loop-distribution -ftree-loop-distribute-patterns @gol -ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize @gol -ftree-loop-vectorize @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 @@ -7716,6 +7723,7 @@ compilation time. -ftree-dce @gol -ftree-dominator-opts @gol -ftree-dse @gol +-ftree-backprop @gol -ftree-forwprop @gol -ftree-fre @gol -ftree-phiprop @gol @@ -8658,6 +8666,13 @@ enabled by default at @option{-O2} and @option{-O3}. Make partial redundancy elimination (PRE) more aggressive. This flag is enabled by default at @option{-O3}. +@item -ftree-backprop +@opindex ftree-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 -ftree-forwprop @opindex ftree-forwprop Perform forward propagation on trees. This flag is enabled by default diff --git a/gcc/fold-const.c b/gcc/fold-const.c index de45a2c..7f00e72 100644 --- a/gcc/fold-const.c +++ b/gcc/fold-const.c @@ -110,7 +110,6 @@ enum comparison_code { COMPCODE_TRUE = 15 }; -static bool negate_mathfn_p (enum built_in_function); static bool negate_expr_p (tree); static tree negate_expr (tree); static tree split_tree (tree, enum tree_code, tree *, tree *, tree *, int); @@ -319,7 +318,7 @@ fold_overflow_warning (const char* gmsgid, enum warn_strict_overflow_code wc) /* Return true if the built-in mathematical function specified by CODE is odd, i.e. -f(x) == f(-x). */ -static bool +bool negate_mathfn_p (enum built_in_function code) { switch (code) diff --git a/gcc/fold-const.h b/gcc/fold-const.h index ee74dc8..4d5b24b 100644 --- a/gcc/fold-const.h +++ b/gcc/fold-const.h @@ -173,6 +173,7 @@ extern tree sign_bit_p (tree, const_tree); extern tree exact_inverse (tree, tree); extern tree const_unop (enum tree_code, tree, tree); extern tree const_binop (enum tree_code, tree, tree, tree); +extern bool negate_mathfn_p (enum built_in_function); /* Return OFF converted to a pointer offset type suitable as offset for POINTER_PLUS_EXPR. Use location LOC for this conversion. */ diff --git a/gcc/passes.def b/gcc/passes.def index dc3f44c..36d2b3b 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -159,6 +159,7 @@ along with GCC; see the file COPYING3. If not see /* After CCP we rewrite no longer addressed locals into SSA form if possible. */ NEXT_PASS (pass_complete_unrolli); + NEXT_PASS (pass_backprop); NEXT_PASS (pass_phiprop); NEXT_PASS (pass_forwprop); NEXT_PASS (pass_object_sizes); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/backprop-1.c b/gcc/testsuite/gcc.dg/tree-ssa/backprop-1.c new file mode 100644 index 0000000..ff88ae8 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/backprop-1.c @@ -0,0 +1,22 @@ +/* { dg-do compile } */ +/* { dg-options "-O -fdump-tree-backprop-details" } */ + +/* Test a simple case of non-looping code in which both uses ignore + the sign and both definitions are sign ops. */ +#define TEST_FUNCTION(TYPE, SUFFIX) \ + TYPE \ + test##SUFFIX (TYPE x, int sel1, int sel2) \ + { \ + TYPE input = sel1 ? -x : __builtin_fabs##SUFFIX (x); \ + if (sel2) \ + return __builtin_cos##SUFFIX (input); \ + else \ + return __builtin_cosh##SUFFIX (input); \ + } + +TEST_FUNCTION (float, f) +TEST_FUNCTION (double, ) +TEST_FUNCTION (long double, l) + +/* { dg-final { scan-tree-dump-times {Deleting[^\n]* = -x} 3 "backprop" } } */ +/* { dg-final { scan-tree-dump-times {Deleting[^\n]* = ABS_EXPR . */ + +/* This pass propagates information that is common to all uses of an SSA + name back up through the sequence of statements that generate it, + simplifying the statements where possible. Sometimes this can expose + fully or partially dead code, but the main focus is simplifying + computations. + + At the moment the pass only handles one piece of information: whether the + sign of a value matters, and therefore whether sign-changing operations + can be skipped. The pass could be extended to more interesting + information in future, such as which bits of an integer are significant. + + For example, take the function: + + double + f (double *a, int n, double start) + { + double x = fabs (start); + for (int i = 0; i < n; ++i) + x *= a[i]; + return __builtin_cos (x); + } + + cos(x) == cos(-x), so the sign of the final x doesn't matter. + That x is the result of a series of multiplications, and if + the sign of the result of a multiplication doesn't matter, + the signs of the inputs don't matter either. + + The pass would replace the incoming value of x (i.e. fabs(start)) + with start. Since there are no other uses of the fabs result, + the call would get deleted as dead. + + The algorithm is: + + (1) Do a post-order traversal of the blocks in the function, walking + each block backwards. For each potentially-simplifiable statement + that defines an SSA name X, examine all uses of X to see what + information is actually significant. Record this as INFO_MAP[X]. + Optimistically ignore for now any back-edge references to + unprocessed phis. + + (2) Iteratively reduce the optimistic result of (1) until we reach + a maximal fixed point (which at the moment would mean revisiting + statements at most once). First push all SSA names that used an + optimistic assumption about a backedge phi onto a worklist. + While the worklist is nonempty, pick off an SSA name X and recompute + INFO_MAP[X]. If the value changes, push all SSA names used in the + definition of X onto the worklist. + + (3) Iterate over each SSA name X with info in INFO_MAP, in the + opposite order to (1), i.e. a forward reverse-post-order walk. + Try to optimize the definition of X using INFO_MAP[X] and fold + the result. (This ensures that we fold definitions before uses.) + + (4) Iterate over each SSA name X with info in INFO_MAP, in the same + order as (1), and delete any statements that are now dead. + (This ensures that if a sequence of statements is dead, + we delete the last statement first.) + + Note that this pass does not deal with direct redundancies, + such as cos(-x)->cos(x). match.pd handles those cases instead. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "gimple-iterator.h" +#include "ssa.h" +#include "fold-const.h" +#include "tree-pass.h" +#include "cfganal.h" +#include "gimple-pretty-print.h" +#include "tree-cfg.h" +#include "tree-ssa-propagate.h" +#include "gimple-fold.h" +#include "alloc-pool.h" +#include "tree-hash-traits.h" + +namespace { + +/* Information about a group of uses of an SSA name. */ +struct usage_info +{ + usage_info () : flag_word (0) {} + usage_info &operator &= (const usage_info &); + usage_info operator & (const usage_info &) const; + bool operator == (const usage_info &) const; + bool operator != (const usage_info &) const; + bool is_useful () const; + + static usage_info intersection_identity (); + + union + { + struct + { + /* True if the uses treat x and -x in the same way. */ + unsigned int ignore_sign : 1; + } flags; + /* All the flag bits as a single int. */ + unsigned int flag_word; + }; +}; + +/* Return an X such that X & Y == Y for all Y. This is the most + optimistic assumption possible. */ + +usage_info +usage_info::intersection_identity () +{ + usage_info ret; + ret.flag_word = -1; + return ret; +} + +/* Intersect *THIS with OTHER, so that *THIS describes all uses covered + by the original *THIS and OTHER. */ + +usage_info & +usage_info::operator &= (const usage_info &other) +{ + flag_word &= other.flag_word; + return *this; +} + +/* Return the intersection of *THIS and OTHER, i.e. a structure that + describes all uses covered by *THIS and OTHER. */ + +usage_info +usage_info::operator & (const usage_info &other) const +{ + usage_info info (*this); + info &= other; + return info; +} + +bool +usage_info::operator == (const usage_info &other) const +{ + return flag_word == other.flag_word; +} + +bool +usage_info::operator != (const usage_info &other) const +{ + return !operator == (other); +} + +/* Return true if *THIS is not simply the default, safe assumption. */ + +bool +usage_info::is_useful () const +{ + return flag_word != 0; +} + +/* Start a dump line about SSA name VAR. */ + +static void +dump_usage_prefix (FILE *file, tree var) +{ + fprintf (file, " "); + print_generic_expr (file, var, 0); + fprintf (file, ": "); +} + +/* Print INFO to FILE. */ + +static void +dump_usage_info (FILE *file, tree var, usage_info *info) +{ + if (info->flags.ignore_sign) + { + dump_usage_prefix (file, var); + fprintf (file, "sign bit not important\n"); + } +} + +/* Represents one execution of the pass. */ +class backprop +{ +public: + backprop (function *); + ~backprop (); + + void execute (); + +private: + const usage_info *lookup_operand (tree); + + void push_to_worklist (tree); + tree pop_from_worklist (); + + void process_builtin_call_use (gcall *, tree, usage_info *); + void process_assign_use (gassign *, tree, usage_info *); + void process_phi_use (gphi *, usage_info *); + void process_use (gimple *, tree, usage_info *); + bool intersect_uses (tree, usage_info *); + void reprocess_inputs (gimple *); + void process_var (tree); + void process_block (basic_block); + + void complete_change (gimple *); + void optimize_builtin_call (gcall *, const usage_info *); + void optimize_assign (gassign *, const usage_info *); + void optimize_phi (gphi *, const usage_info *); + + typedef hash_map info_map_type; + typedef std::pair var_info_pair; + + /* The function we're optimizing. */ + function *m_fn; + + /* Pool for allocating usage_info structures. */ + object_allocator m_info_pool; + + /* Maps an SSA name to a description of all uses of that SSA name. + All the usage_infos satisfy is_useful. */ + info_map_type m_info_map; + + /* Post-ordered list of all potentially-interesting SSA names, + along with information that describes all uses. */ + auto_vec m_vars; + + /* A bitmap of blocks that we have finished processing in the initial + post-order walk. */ + sbitmap m_visited_blocks; + + /* A worklist of SSA names whose definitions need to be reconsidered. */ + auto_vec m_worklist; + + /* The SSA names in M_WORKLIST, identified by their SSA_NAME_VERSION. */ + bitmap m_worklist_names; +}; + +backprop::backprop (function *fn) + : m_fn (fn), + m_info_pool ("usage_info"), + m_visited_blocks (sbitmap_alloc (last_basic_block_for_fn (m_fn))), + m_worklist_names (BITMAP_ALLOC (NULL)) +{ + bitmap_clear (m_visited_blocks); +} + +backprop::~backprop () +{ + BITMAP_FREE (m_worklist_names); + sbitmap_free (m_visited_blocks); + m_info_pool.release (); +} + +/* Return usage information for general operand OP, or null if none. */ + +const usage_info * +backprop::lookup_operand (tree op) +{ + if (op && TREE_CODE (op) == SSA_NAME) + if (usage_info **slot = m_info_map.get (op)) + return *slot; + return NULL; +} + +/* Add SSA name VAR to the worklist, if it isn't on the worklist already. */ + +void +backprop::push_to_worklist (tree var) +{ + if (!bitmap_set_bit (m_worklist_names, SSA_NAME_VERSION (var))) + return; + m_worklist.safe_push (var); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "[WORKLIST] Pushing "); + print_generic_expr (dump_file, var, 0); + fprintf (dump_file, "\n"); + } +} + +/* Remove and return the next SSA name from the worklist. The worklist + is known to be nonempty. */ + +tree +backprop::pop_from_worklist () +{ + tree var = m_worklist.pop (); + bitmap_clear_bit (m_worklist_names, SSA_NAME_VERSION (var)); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "[WORKLIST] Popping "); + print_generic_expr (dump_file, var, 0); + fprintf (dump_file, "\n"); + } + return var; +} + +/* Make INFO describe all uses of RHS in CALL, which is a call to a + built-in function. */ + +void +backprop::process_builtin_call_use (gcall *call, tree rhs, usage_info *info) +{ + enum built_in_function fn = DECL_FUNCTION_CODE (gimple_call_fndecl (call)); + tree lhs = gimple_call_lhs (call); + switch (fn) + { + CASE_FLT_FN (BUILT_IN_COS): + CASE_FLT_FN (BUILT_IN_COSH): + CASE_FLT_FN (BUILT_IN_CCOS): + CASE_FLT_FN (BUILT_IN_CCOSH): + CASE_FLT_FN (BUILT_IN_HYPOT): + /* The signs of all inputs are ignored. */ + info->flags.ignore_sign = true; + break; + + CASE_FLT_FN (BUILT_IN_COPYSIGN): + /* The sign of the first input is ignored. */ + if (rhs != gimple_call_arg (call, 1)) + info->flags.ignore_sign = true; + break; + + CASE_FLT_FN (BUILT_IN_POW): + { + /* The sign of the first input is ignored as long as the second + input is an even real. */ + tree power = gimple_call_arg (call, 1); + HOST_WIDE_INT n; + if (TREE_CODE (power) == REAL_CST + && real_isinteger (&TREE_REAL_CST (power), &n) + && (n & 1) == 0) + info->flags.ignore_sign = true; + break; + } + + CASE_FLT_FN (BUILT_IN_FMA): + /* In X * X + Y, where Y is distinct from X, the sign of X doesn't + matter. */ + if (gimple_call_arg (call, 0) == rhs + && gimple_call_arg (call, 1) == rhs + && gimple_call_arg (call, 2) != rhs) + info->flags.ignore_sign = true; + break; + + default: + if (negate_mathfn_p (fn)) + /* The sign of the (single) input doesn't matter provided + that the sign of the output doesn't matter. */ + if (const usage_info *lhs_info = lookup_operand (lhs)) + info->flags.ignore_sign = lhs_info->flags.ignore_sign; + break; + } +} + +/* Make INFO describe all uses of RHS in ASSIGN. */ + +void +backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info) +{ + tree lhs = gimple_assign_lhs (assign); + switch (gimple_assign_rhs_code (assign)) + { + case ABS_EXPR: + /* The sign of the input doesn't matter. */ + info->flags.ignore_sign = true; + break; + + case COND_EXPR: + /* For A = B ? C : D, propagate information about all uses of A + to B and C. */ + if (rhs != gimple_assign_rhs1 (assign)) + if (const usage_info *lhs_info = lookup_operand (lhs)) + *info = *lhs_info; + break; + + case FMA_EXPR: + /* In X * X + Y, where Y is distinct from X, the sign of X doesn't + matter. */ + if (gimple_assign_rhs1 (assign) == rhs + && gimple_assign_rhs2 (assign) == rhs + && gimple_assign_rhs3 (assign) != rhs) + info->flags.ignore_sign = true; + break; + + case MULT_EXPR: + /* In X * X, the sign of X doesn't matter. */ + if (gimple_assign_rhs1 (assign) == rhs + && gimple_assign_rhs2 (assign) == rhs) + info->flags.ignore_sign = true; + /* Fall through. */ + + case NEGATE_EXPR: + case RDIV_EXPR: + /* If the sign of the result doesn't matter, the sign of the inputs + doesn't matter either. */ + if (FLOAT_TYPE_P (TREE_TYPE (rhs))) + if (const usage_info *lhs_info = lookup_operand (lhs)) + info->flags.ignore_sign = lhs_info->flags.ignore_sign; + break; + + default: + break; + } +} + +/* Make INFO describe the uses of PHI's result. */ + +void +backprop::process_phi_use (gphi *phi, usage_info *info) +{ + tree result = gimple_phi_result (phi); + if (const usage_info *result_info = lookup_operand (result)) + *info = *result_info; +} + +/* Make INFO describe all uses of RHS in STMT. */ + +void +backprop::process_use (gimple *stmt, tree rhs, usage_info *info) +{ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "[USE] "); + print_generic_expr (dump_file, rhs, 0); + fprintf (dump_file, " in "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + + if (gcall *call = dyn_cast (stmt)) + { + if (gimple_call_builtin_p (call, BUILT_IN_NORMAL)) + process_builtin_call_use (call, rhs, info); + } + else if (gassign *assign = dyn_cast (stmt)) + process_assign_use (assign, rhs, info); + else if (gphi *phi = dyn_cast (stmt)) + process_phi_use (phi, info); + + if (dump_file && (dump_flags & TDF_DETAILS)) + dump_usage_info (dump_file, rhs, info); +} + +/* Make INFO describe all uses of VAR, returning true if the result + is useful. If the uses include phis that haven't been processed yet, + make the most optimistic assumption possible, so that we aim for + a maximum rather than a minimum fixed point. */ + +bool +backprop::intersect_uses (tree var, usage_info *info) +{ + imm_use_iterator iter; + gimple *stmt; + *info = usage_info::intersection_identity (); + FOR_EACH_IMM_USE_STMT (stmt, iter, var) + { + if (is_a (stmt) + && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index)) + { + /* Skip unprocessed phis. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "[BACKEDGE] "); + print_generic_expr (dump_file, var, 0); + fprintf (dump_file, " in "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + } + else + { + usage_info subinfo; + process_use (stmt, var, &subinfo); + *info &= subinfo; + if (!info->is_useful ()) + { + BREAK_FROM_IMM_USE_STMT (iter); + return false; + } + } + } + return true; +} + +/* Queue for reconsideration any input of STMT that has information + associated with it. This is used if that information might be + too optimistic. */ + +void +backprop::reprocess_inputs (gimple *stmt) +{ + use_operand_p use_p; + ssa_op_iter oi; + FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE) + { + tree var = get_use_from_ptr (use_p); + if (lookup_operand (var)) + push_to_worklist (var); + } +} + +/* Say that we're recording INFO for SSA name VAR, or that we're deleting + existing information if INFO is null. INTRO describes the change. */ + +static void +dump_var_info (tree var, usage_info *info, const char *intro) +{ + fprintf (dump_file, "[DEF] %s for ", intro); + print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM); + if (info) + dump_usage_info (dump_file, var, info); +} + +/* Process all uses of VAR and record or update the result in + M_INFO_MAP and M_VARS. */ + +void +backprop::process_var (tree var) +{ + if (has_zero_uses (var)) + return; + + usage_info info; + intersect_uses (var, &info); + + gimple *stmt = SSA_NAME_DEF_STMT (var); + if (info.is_useful ()) + { + bool existed; + usage_info *&map_info = m_info_map.get_or_insert (var, &existed); + if (!existed) + { + /* Recording information about VAR for the first time. */ + map_info = m_info_pool.allocate (); + *map_info = info; + m_vars.safe_push (var_info_pair (var, map_info)); + if (dump_file && (dump_flags & TDF_DETAILS)) + dump_var_info (var, map_info, "Recording new information"); + + /* If STMT is a phi, reprocess any backedge uses. This is a + no-op for other uses, which won't have any information + associated with them. */ + if (is_a (stmt)) + reprocess_inputs (stmt); + } + else if (info != *map_info) + { + /* Recording information that is less optimistic than before. */ + gcc_checking_assert ((info & *map_info) == info); + *map_info = info; + if (dump_file && (dump_flags & TDF_DETAILS)) + dump_var_info (var, map_info, "Updating information"); + reprocess_inputs (stmt); + } + } + else + { + if (usage_info **slot = m_info_map.get (var)) + { + /* Removing previously-recorded information. */ + **slot = info; + m_info_map.remove (var); + if (dump_file && (dump_flags & TDF_DETAILS)) + dump_var_info (var, NULL, "Deleting information"); + reprocess_inputs (stmt); + } + else + { + /* If STMT is a phi, remove any information recorded for + its arguments. */ + if (is_a (stmt)) + reprocess_inputs (stmt); + } + } +} + +/* Process all statements and phis in BB, during the first post-order walk. */ + +void +backprop::process_block (basic_block bb) +{ + for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi); + gsi_prev (&gsi)) + { + tree lhs = gimple_get_lhs (gsi_stmt (gsi)); + if (lhs && TREE_CODE (lhs) == SSA_NAME) + process_var (lhs); + } + for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi); + gsi_next (&gpi)) + process_var (gimple_phi_result (gpi.phi ())); +} + +/* Delete the definition of VAR, which has no uses. */ + +static void +remove_unused_var (tree var) +{ + gimple *stmt = SSA_NAME_DEF_STMT (var); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Deleting "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); + } + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + gsi_remove (&gsi, true); + release_ssa_name (var); +} + +/* Note that we're replacing OLD_RHS with NEW_RHS in STMT. */ + +static void +note_replacement (gimple *stmt, tree old_rhs, tree new_rhs) +{ + fprintf (dump_file, "Replacing use of "); + print_generic_expr (dump_file, old_rhs, 0); + fprintf (dump_file, " with "); + print_generic_expr (dump_file, new_rhs, 0); + fprintf (dump_file, " in "); + print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); +} + +/* If RHS is an SSA name whose definition just changes the sign of a value, + return that other value, otherwise return null. */ + +static tree +strip_sign_op_1 (tree rhs) +{ + if (TREE_CODE (rhs) != SSA_NAME) + return NULL_TREE; + + gimple *def_stmt = SSA_NAME_DEF_STMT (rhs); + if (gassign *assign = dyn_cast (def_stmt)) + switch (gimple_assign_rhs_code (assign)) + { + case ABS_EXPR: + case NEGATE_EXPR: + return gimple_assign_rhs1 (assign); + + default: + break; + } + else if (gcall *call = dyn_cast (def_stmt)) + { + if (gimple_call_builtin_p (call, BUILT_IN_NORMAL)) + switch (DECL_FUNCTION_CODE (gimple_call_fndecl (call))) + { + CASE_FLT_FN (BUILT_IN_COPYSIGN): + return gimple_call_arg (call, 0); + + default: + break; + } + } + + return NULL_TREE; +} + +/* If RHS is an SSA name whose definition just changes the sign of a value, + strip all such operations and return the ultimate input to them. + Return null otherwise. + + Although this could in principle lead to quadratic searching, + in practice a long sequence of sign manipulations should already + have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search + for more than one operation in order to catch cases like -abs(x). */ + +static tree +strip_sign_op (tree rhs) +{ + tree new_rhs = strip_sign_op_1 (rhs); + if (!new_rhs) + return NULL_TREE; + while (tree next = strip_sign_op_1 (new_rhs)) + new_rhs = next; + return new_rhs; +} + +/* Strip all sign operations from the rvalue at *RHS_PTR in STMT. + Return true if something changed. The caller is responsible + for the necessary bookkeeping. */ + +static bool +strip_sign_op (gimple *stmt, tree *rhs_ptr) +{ + if (tree new_rhs = strip_sign_op (*rhs_ptr)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + note_replacement (stmt, *rhs_ptr, new_rhs); + *rhs_ptr = new_rhs; + return true; + } + return false; +} + +/* STMT has been changed. Give the fold machinery a chance to simplify + and canonicalize it (e.g. by ensuring that commutative operands have + the right order), then record the updates. */ + +void +backprop::complete_change (gimple *stmt) +{ + gimple_stmt_iterator gsi = gsi_for_stmt (stmt); + if (fold_stmt (&gsi)) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, " which folds to: "); + print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM); + } + } + update_stmt (gsi_stmt (gsi)); +} + +/* Optimize CALL, a call to a built-in function, on the basis that INFO + describes all uses of the LHS. */ + +void +backprop::optimize_builtin_call (gcall *call, const usage_info *info) +{ + bool changed_p = false; + enum built_in_function fn = DECL_FUNCTION_CODE (gimple_call_fndecl (call)); + /* If we have an f such that -f(x) = f(-x), and if the sign of the result + doesn't matter, strip any sign operations from the input. */ + if (info->flags.ignore_sign + && negate_mathfn_p (fn) + && strip_sign_op (call, gimple_call_arg_ptr (call, 0))) + changed_p = true; + if (changed_p) + complete_change (call); +} + +/* Optimize ASSIGN on the basis that INFO describes all uses of the lhs. */ + +void +backprop::optimize_assign (gassign *assign, const usage_info *info) +{ + bool changed_p = false; + switch (gimple_assign_rhs_code (assign)) + { + case MULT_EXPR: + case RDIV_EXPR: + /* If the sign of the result doesn't matter, strip sign operations + from both inputs. */ + if (info->flags.ignore_sign + && (strip_sign_op (assign, gimple_assign_rhs1_ptr (assign)) + || strip_sign_op (assign, gimple_assign_rhs2_ptr (assign)))) + changed_p = true; + break; + + case COND_EXPR: + /* If the sign of A ? B : C doesn't matter, strip sign operations + from both B and C. */ + if (info->flags.ignore_sign + && (strip_sign_op (assign, gimple_assign_rhs2_ptr (assign)) + || strip_sign_op (assign, gimple_assign_rhs3_ptr (assign)))) + changed_p = true; + break; + + default: + break; + } + if (changed_p) + complete_change (assign); +} + +/* Optimize PHI on the basis that INFO describes all uses of the result. */ + +void +backprop::optimize_phi (gphi *phi, const usage_info *info) +{ + /* If the sign of the result doesn't matter, strip sign operations + from all arguments. */ + if (info->flags.ignore_sign) + { + use_operand_p use; + ssa_op_iter oi; + FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE) + if (tree new_arg = strip_sign_op (USE_FROM_PTR (use))) + { + if (dump_file && (dump_flags & TDF_DETAILS)) + note_replacement (phi, USE_FROM_PTR (use), new_arg); + replace_exp (use, new_arg); + } + } +} + +void +backprop::execute () +{ + /* Phase 1: Traverse the function, making optimistic assumptions + about any phi whose definition we haven't seen. */ + int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn)); + unsigned int postorder_num = post_order_compute (postorder, false, false); + for (unsigned int i = 0; i < postorder_num; ++i) + { + process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i])); + bitmap_set_bit (m_visited_blocks, postorder[i]); + } + XDELETEVEC (postorder); + + /* Phase 2: Use the initial (perhaps overly optimistic) information + to create a maximal fixed point solution. */ + while (!m_worklist.is_empty ()) + process_var (pop_from_worklist ()); + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\n"); + + /* Phase 3: Do a reverse post-order walk, using information about + the uses of SSA names to optimize their definitions. */ + for (unsigned int i = m_vars.length (); i-- > 0;) + { + usage_info *info = m_vars[i].second; + if (info->is_useful ()) + { + tree var = m_vars[i].first; + gimple *stmt = SSA_NAME_DEF_STMT (var); + if (gcall *call = dyn_cast (stmt)) + { + if (gimple_call_builtin_p (call, BUILT_IN_NORMAL)) + optimize_builtin_call (call, info); + } + else if (gassign *assign = dyn_cast (stmt)) + optimize_assign (assign, info); + else if (gphi *phi = dyn_cast (stmt)) + optimize_phi (phi, info); + } + } + + /* Phase 4: Do a post-order walk, deleting statements that are no + longer needed. */ + for (unsigned int i = 0; i < m_vars.length (); ++i) + { + tree var = m_vars[i].first; + if (has_zero_uses (var)) + remove_unused_var (var); + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "\n"); +} + +const pass_data pass_data_backprop = +{ + GIMPLE_PASS, /* type */ + "backprop", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_TREE_BACKPROP, /* tv_id */ + ( PROP_cfg | PROP_ssa ), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ +}; + +class pass_backprop : public gimple_opt_pass +{ +public: + pass_backprop (gcc::context *ctxt) + : gimple_opt_pass (pass_data_backprop, ctxt) + {} + + /* opt_pass methods: */ + opt_pass * clone () { return new pass_backprop (m_ctxt); } + virtual bool gate (function *) { return flag_tree_backprop; } + virtual unsigned int execute (function *); + +}; // class pass_backprop + +unsigned int +pass_backprop::execute (function *fn) +{ + backprop (fn).execute (); + return 0; +} + +} // anon namespace + +gimple_opt_pass * +make_pass_backprop (gcc::context *ctxt) +{ + return new pass_backprop (ctxt); +}