From patchwork Fri Aug 13 01:33:44 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Giuseppe Scrivano X-Patchwork-Id: 61658 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 B1A72B70AA for ; Fri, 13 Aug 2010 11:34:13 +1000 (EST) Received: (qmail 4192 invoked by alias); 13 Aug 2010 01:34:11 -0000 Received: (qmail 4176 invoked by uid 22791); 13 Aug 2010 01:34:10 -0000 X-SWARE-Spam-Status: No, hits=-1.2 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, SPF_HELO_PASS, SPF_NEUTRAL, TW_TM, T_TO_NO_BRKTS_FREEMAIL 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; Fri, 13 Aug 2010 01:34:04 +0000 Received: from valhalla.homenet (84.222.166.247) by jack.mail.tiscali.it (8.5.124) id 4C4EAE83006284E8; Fri, 13 Aug 2010 03:34:01 +0200 Received: from gscrivano by valhalla.homenet with local (Exim 4.72) (envelope-from ) id 1Ojj9U-0005m4-B9; Fri, 13 Aug 2010 03:33:44 +0200 From: Giuseppe Scrivano To: gcc-patches@gcc.gnu.org Subject: [PATCH] tailcall: Handle NEGATE_EXPR and MINUS_EXPR Date: Fri, 13 Aug 2010 03:33:44 +0200 Message-ID: <87vd7ffg93.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 Hello, I have attached a small patch, now the tail call optimizator handles NEGATE_EXPR and MINUS_EXPR too. Bootstrapped and regtested on i686-linux. Cheers, 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..cdda9fa 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,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 (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); + *ass_var = dest; + } + 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..8c37d67 --- /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 (11) != -39916789) + abort (); + + if (bar (11) != -39916800) + 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" } } */