From patchwork Tue Aug 24 15:43:48 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuseppe Scrivano X-Patchwork-Id: 62606 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]) by ozlabs.org (Postfix) with SMTP id 913FDB70D4 for ; Wed, 25 Aug 2010 01:47:18 +1000 (EST) Received: (qmail 16220 invoked by alias); 24 Aug 2010 15:47:16 -0000 Received: (qmail 16209 invoked by uid 22791); 24 Aug 2010 15:47:15 -0000 X-SWARE-Spam-Status: No, hits=-1.1 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_NEUTRAL, TW_TM X-Spam-Check-By: sourceware.org Received: from averell.mail.tiscali.it (HELO averell.mail.tiscali.it) (213.205.33.55) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Tue, 24 Aug 2010 15:47:08 +0000 Received: from valhalla.homenet (84.222.169.251) by averell.mail.tiscali.it (8.5.124) id 4C4EAB6500B4F4B6; Tue, 24 Aug 2010 17:47:04 +0200 Received: from gscrivano by valhalla.homenet with local (Exim 4.72) (envelope-from ) id 1OnvfA-000673-Ge; Tue, 24 Aug 2010 17:43:48 +0200 From: Giuseppe Scrivano To: Richard Guenther , Zdenek Dvorak Cc: gcc-patches@gcc.gnu.org Subject: Re: [PING][PATCH] tailcall: Handle NEGATE_EXPR and MINUS_EXPR References: <87vd7ffg93.fsf@valhalla.homenet> <4C692D1A.8040004@oracle.com> <878w46616e.fsf@valhalla.homenet> <87wrrht5pf.fsf_-_@valhalla.homenet> Date: Tue, 24 Aug 2010 17:43:48 +0200 In-Reply-To: (Richard Guenther's message of "Tue, 24 Aug 2010 11:49:49 +0200") Message-ID: <87occsyq17.fsf@valhalla.homenet> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (gnu/linux) MIME-Version: 1.0 X-IsSubscribed: yes 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 Thanks for your comments. I have modified the patch following them. bootstrapped and regtested on i686-linux. Giuseppe gcc/ChangeLog 2010-08-24 Giuseppe Scrivano * tree-tailcall.c (process_assignment): Handle NEGATE_EXPR and MINUS_EXPR. gcc/testsuite/ChangeLog 2010-08-24 Giuseppe Scrivano * gcc.dg/tree-ssa/tailrecursion-7.c: New file. diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c index 65eaa40..7fdab62 100644 --- a/gcc/tree-tailcall.c +++ b/gcc/tree-tailcall.c @@ -252,7 +252,7 @@ static bool process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m, tree *a, tree *ass_var) { - tree op0, op1, non_ass_var; + tree op0, op1 = NULL, non_ass_var = NULL; tree dest = gimple_assign_lhs (stmt); enum tree_code code = gimple_assign_rhs_code (stmt); enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code); @@ -278,8 +278,20 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m, return true; } - if (rhs_class != GIMPLE_BINARY_RHS) - return false; + switch (rhs_class) + { + case GIMPLE_BINARY_RHS: + op1 = gimple_assign_rhs2 (stmt); + + /* Fall through. */ + + case GIMPLE_UNARY_RHS: + op0 = gimple_assign_rhs1 (stmt); + break; + + default: + return false; + } /* Accumulator optimizations will reverse the order of operations. We can only do that for floating-point types if we're assuming @@ -288,20 +300,9 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m, if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl)))) return false; - /* We only handle the code like - - x = call (); - y = m * x; - z = y + a; - return z; - - TODO -- Extend it for cases where the linear transformation of the output - is expressed in a more complicated way. */ - - op0 = gimple_assign_rhs1 (stmt); - op1 = gimple_assign_rhs2 (stmt); - - if (op0 == *ass_var + if (rhs_class == GIMPLE_UNARY_RHS) + ; + else if (op0 == *ass_var && (non_ass_var = independent_of_stmt_p (op1, stmt, call))) ; else if (op1 == *ass_var @@ -322,8 +323,32 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m, *ass_var = dest; return true; - /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR, - POINTER_PLUS_EXPR). */ + case NEGATE_EXPR: + if (FLOAT_TYPE_P (TREE_TYPE (op0))) + *m = build_real (TREE_TYPE (op0), dconstm1); + else + *m = build_int_cst (TREE_TYPE (op0), -1); + + *ass_var = dest; + return true; + + case MINUS_EXPR: + if (*ass_var == op0) + *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var); + else + { + if (FLOAT_TYPE_P (TREE_TYPE (non_ass_var))) + *m = build_real (TREE_TYPE (non_ass_var), dconstm1); + else + *m = build_int_cst (TREE_TYPE (non_ass_var), -1); + + *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var); + } + + *ass_var = dest; + return true; + + /* TODO -- Handle POINTER_PLUS_EXPR. */ default: return false; diff --git a/./gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-7.c b/./gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-7.c new file mode 100644 index 0000000..875a6aa --- /dev/null +++ b/./gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-7.c @@ -0,0 +1,40 @@ +/* { dg-do run } */ +/* { dg-options "-O1 -foptimize-sibling-calls -fdump-tree-optimized" } */ + +extern void abort (void); +extern void exit (int); + +int foo (int n) +{ + return n == 0 ? 1 : n * (n - foo (n - 1)); +} + +int bar (int n) +{ + return n == 0 ? 1 : n * (- bar (n - 1)); +} + +int baz (int n, int m) +{ + return n == 0 ? 100 : (baz (n - 1, m) - m); +} + +int main (void) +{ + if (foo (6) != 726) + abort (); + + if (bar (7) != -5040) + abort (); + + if (baz (10, 5) != 50) + abort (); + + exit (0); +} + +/* { dg-final { scan-tree-dump-times "\\mfoo\\M" 4 "optimized"} } */ +/* { dg-final { scan-tree-dump-times "\\mbar\\M" 4 "optimized"} } */ +/* { dg-final { scan-tree-dump-times "\\mbaz\\M" 4 "optimized"} } */ + +/* { dg-final { cleanup-tree-dump "optimized" } } */