From patchwork Fri Jun 25 11:51:14 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jakub Jelinek X-Patchwork-Id: 56904 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 D0D81B6F16 for ; Fri, 25 Jun 2010 21:50:49 +1000 (EST) Received: (qmail 23255 invoked by alias); 25 Jun 2010 11:50:47 -0000 Received: (qmail 23191 invoked by uid 22791); 25 Jun 2010 11:50:42 -0000 X-SWARE-Spam-Status: No, hits=-6.0 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, TW_CF, TW_TM, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 25 Jun 2010 11:50:36 +0000 Received: from int-mx05.intmail.prod.int.phx2.redhat.com (int-mx05.intmail.prod.int.phx2.redhat.com [10.5.11.18]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id o5PBoYV4000920 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Fri, 25 Jun 2010 07:50:34 -0400 Received: from tyan-ft48-01.lab.bos.redhat.com (tyan-ft48-01.lab.bos.redhat.com [10.16.42.4]) by int-mx05.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id o5PBoXF4024196 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Fri, 25 Jun 2010 07:50:34 -0400 Received: from tyan-ft48-01.lab.bos.redhat.com (tyan-ft48-01.lab.bos.redhat.com [127.0.0.1]) by tyan-ft48-01.lab.bos.redhat.com (8.14.4/8.14.4) with ESMTP id o5PBpFFV025073; Fri, 25 Jun 2010 13:51:15 +0200 Received: (from jakub@localhost) by tyan-ft48-01.lab.bos.redhat.com (8.14.4/8.14.4/Submit) id o5PBpFBD025071; Fri, 25 Jun 2010 13:51:15 +0200 Date: Fri, 25 Jun 2010 13:51:14 +0200 From: Jakub Jelinek To: Richard Guenther , Zdenek Dvorak Cc: gcc-patches@gcc.gnu.org Subject: [PATCH] Unswitching fixes (PR middle-end/43866) Message-ID: <20100625115114.GJ12443@tyan-ft48-01.lab.bos.redhat.com> Reply-To: Jakub Jelinek MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-12-10) 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! This patch fixes a couple of problems in tree-ssa-loop-unswitch.c. The first problem is in tree_may_unswitch_on - a tuplification error. Result of build2 (cond_code, ...) is never integer_zerop nor integer_nonzerop. While we could fold, we can just test for the canonical true/false conditions using gimple_cond* predicates. Another problem is that when hitting --param max-unswitch-level nesting level we wouldn't adjust the conditions. Some further pass probably would do so, but when we already have the code to handle it, it is IMHO better to do it right away. When hitting the max level we just won't consider any new conditions for unswitching. The last issue is that there is no cfg cleanup in between the unswitching levels, which means we often choose conditions that are never tested in any reachable bb in the loop. Instead of doing cfg cleanup and updating everything, this patch just does a quick discovery of reachable bbs in the loop (which takes into account the modified conditions) and doesn't consider conditions that aren't reachable. Bootstrapped/regtested on x86_64-linux and i686-linux. Ok for trunk? 2010-06-25 Jakub Jelinek PR middle-end/43866 * tree-ssa-loop-unswitch.c (tree_may_unswitch_on): If stmt is always true or always false, return NULL_TREE. (tree_unswitch_single_loop): Optimize conditions even when reaching max-unswitch-level parameter. If num > 0, optimize first all conditions using entry checks, then do still reachable block discovery and consider only conditions in still reachable basic blocks in the loop. * gfortran.dg/pr43866.f90: New test. Jakub --- gcc/tree-ssa-loop-unswitch.c.jj 2010-06-07 11:25:05.000000000 +0200 +++ gcc/tree-ssa-loop-unswitch.c 2010-06-24 17:25:09.000000000 +0200 @@ -129,6 +129,12 @@ tree_may_unswitch_on (basic_block bb, st if (!stmt || gimple_code (stmt) != GIMPLE_COND) return NULL_TREE; + /* To keep the things simple, we do not directly remove the conditions, + but just replace tests with 0 != 0 resp. 1 != 0. Prevent the infinite + loop where we would unswitch again on such a condition. */ + if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt)) + return NULL_TREE; + /* Condition must be invariant. */ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) { @@ -142,12 +148,6 @@ tree_may_unswitch_on (basic_block bb, st cond = build2 (gimple_cond_code (stmt), boolean_type_node, gimple_cond_lhs (stmt), gimple_cond_rhs (stmt)); - /* To keep the things simple, we do not directly remove the conditions, - but just replace tests with 0/1. Prevent the infinite loop where we - would unswitch again on such a condition. */ - if (integer_zerop (cond) || integer_nonzerop (cond)) - return NULL_TREE; - return cond; } @@ -193,21 +193,14 @@ tree_unswitch_single_loop (struct loop * { basic_block *bbs; struct loop *nloop; - unsigned i; + unsigned i, found; tree cond = NULL_TREE; gimple stmt; bool changed = false; - /* Do not unswitch too much. */ - if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); - return false; - } - i = 0; bbs = get_loop_body (loop); + found = loop->num_nodes; while (1) { @@ -218,8 +211,17 @@ tree_unswitch_single_loop (struct loop * if (i == loop->num_nodes) { - free (bbs); - return changed; + if (dump_file + && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL) + && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, ";; Not unswitching anymore, hit max level\n"); + + if (found == loop->num_nodes) + { + free (bbs); + return changed; + } + break; } cond = simplify_using_entry_checks (loop, cond); @@ -236,19 +238,107 @@ tree_unswitch_single_loop (struct loop * gimple_cond_set_condition_from_tree (stmt, boolean_false_node); changed = true; } + /* Do not unswitch too much. */ + else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)) + { + i++; + continue; + } + /* In nested tree_unswitch_single_loop first optimize all conditions + using entry checks, then discover still reachable blocks in the + loop and find the condition only among those still reachable bbs. */ + else if (num != 0) + { + if (found == loop->num_nodes) + found = i; + i++; + continue; + } else - break; + { + found = i; + break; + } update_stmt (stmt); i++; } + if (num != 0) + { + basic_block *tos, *worklist; + + /* When called recursively, first do a quick discovery + of reachable bbs after the above changes and only + consider conditions in still reachable bbs. */ + tos = worklist = XNEWVEC (basic_block, loop->num_nodes); + + for (i = 0; i < loop->num_nodes; i++) + bbs[i]->flags &= ~BB_REACHABLE; + + /* Start with marking header. */ + *tos++ = bbs[0]; + bbs[0]->flags |= BB_REACHABLE; + + /* Iterate: find everything reachable from what we've already seen + within the same innermost loop. Don't look through false edges + if condition is always true or true edges if condition is + always false. */ + while (tos != worklist) + { + basic_block b = *--tos; + edge e; + edge_iterator ei; + int flags = 0; + + if (EDGE_COUNT (b->succs) == 2) + { + gimple stmt = last_stmt (b); + if (stmt + && gimple_code (stmt) == GIMPLE_COND) + { + if (gimple_cond_true_p (stmt)) + flags = EDGE_FALSE_VALUE; + else if (gimple_cond_false_p (stmt)) + flags = EDGE_TRUE_VALUE; + } + } + + FOR_EACH_EDGE (e, ei, b->succs) + { + basic_block dest = e->dest; + + if (dest->loop_father == loop + && !(dest->flags & BB_REACHABLE) + && !(e->flags & flags)) + { + *tos++ = dest; + dest->flags |= BB_REACHABLE; + } + } + } + + free (worklist); + + /* Find a bb to unswitch on. */ + for (; found < loop->num_nodes; found++) + if ((bbs[found]->flags & BB_REACHABLE) + && (cond = tree_may_unswitch_on (bbs[found], loop))) + break; + + if (found == loop->num_nodes) + { + free (bbs); + return changed; + } + } + if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, ";; Unswitching loop\n"); initialize_original_copy_tables (); /* Unswitch the loop on this condition. */ - nloop = tree_unswitch_loop (loop, bbs[i], cond); + nloop = tree_unswitch_loop (loop, bbs[found], cond); if (!nloop) { free_original_copy_tables (); --- gcc/testsuite/gfortran.dg/pr43866.f90.jj 2010-06-25 09:51:40.000000000 +0200 +++ gcc/testsuite/gfortran.dg/pr43866.f90 2010-06-25 09:53:29.000000000 +0200 @@ -0,0 +1,43 @@ +! PR middle-end/43866 +! { dg-do run } +! { dg-options "-funswitch-loops -fbounds-check" } + +MODULE PR43866 + IMPLICIT NONE + TYPE TT + REAL(KIND=4), DIMENSION(:,:), POINTER :: A + REAL(KIND=8), DIMENSION(:,:), POINTER :: B + END TYPE +CONTAINS + SUBROUTINE FOO(M,X,Y,T) + TYPE(TT), POINTER :: M + INTEGER, INTENT(IN) :: Y, X + INTEGER :: C, D + LOGICAL :: T + REAL(KIND = 4), DIMENSION(:,:), POINTER :: P + REAL(KIND = 8), DIMENSION(:,:), POINTER :: Q + + Q => M%B + P => M%A + DO C=1,X + DO D=C+1,Y + IF (T) THEN + P(D,C)=P(C,D) + ELSE + Q(D,C)=Q(C,D) + ENDIF + ENDDO + ENDDO + END SUBROUTINE FOO +END MODULE PR43866 + + USE PR43866 + TYPE(TT), POINTER :: Q + INTEGER, PARAMETER :: N=17 + ALLOCATE (Q) + ALLOCATE (Q%B(N,N)) + Q%B=0 + CALL FOO (Q,N,N,.FALSE.) +END + +! { dg-final { cleanup-modules "pr43866" } }