From patchwork Mon Aug 16 15:13:13 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuseppe Scrivano X-Patchwork-Id: 61811 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 852D2B70AF for ; Tue, 17 Aug 2010 01:13:56 +1000 (EST) Received: (qmail 27709 invoked by alias); 16 Aug 2010 15:13:52 -0000 Received: (qmail 27698 invoked by uid 22791); 16 Aug 2010 15:13:51 -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 jack.mail.tiscali.it (HELO jack.mail.tiscali.it) (213.205.33.53) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 16 Aug 2010 15:13:45 +0000 Received: from valhalla.homenet (84.222.166.247) by jack.mail.tiscali.it (8.5.124) id 4C4EAE83006FE716; Mon, 16 Aug 2010 17:13:35 +0200 Received: from gscrivano by valhalla.homenet with local (Exim 4.72) (envelope-from ) id 1Ol1NB-0007zw-8E; Mon, 16 Aug 2010 17:13:13 +0200 From: Giuseppe Scrivano To: Paolo Carlini Cc: gcc-patches@gcc.gnu.org Subject: Re: [PATCH] tailcall: Handle NEGATE_EXPR and MINUS_EXPR References: <87vd7ffg93.fsf@valhalla.homenet> <4C692D1A.8040004@oracle.com> Date: Mon, 16 Aug 2010 17:13:13 +0200 In-Reply-To: <4C692D1A.8040004@oracle.com> (Paolo Carlini's message of "Mon, 16 Aug 2010 14:20:42 +0200") Message-ID: <878w46616e.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 Hi Paolo, thanks for the review. I have changed the patch accordingly. Giuseppe gcc/ChangeLog 2010-08-13 Giuseppe Scrivano * tree-tailcall.c (process_assignment): Handle NEGATE_EXPR and MINUS_EXPR. gcc/testsuite/ChangeLog 2010-08-13 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..fadcafe 100644 --- a/gcc/tree-tailcall.c +++ b/gcc/tree-tailcall.c @@ -278,9 +278,6 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m, return true; } - if (rhs_class != GIMPLE_BINARY_RHS) - return false; - /* Accumulator optimizations will reverse the order of operations. We can only do that for floating-point types if we're assuming that addition and multiplication are associative. */ @@ -288,20 +285,12 @@ 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) + non_ass_var = op0; + else if (op0 == *ass_var && (non_ass_var = independent_of_stmt_p (op1, stmt, call))) ; else if (op1 == *ass_var @@ -322,8 +311,31 @@ 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 (non_ass_var))) + return false; + + *m = build_int_cst (TREE_TYPE (non_ass_var), -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))) + return false; + + *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" } } */