From patchwork Wed Apr 3 13:38:25 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Biener X-Patchwork-Id: 233464 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 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 7D32F2C00C2 for ; Thu, 4 Apr 2013 00:39:31 +1100 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=DxZxMwL3dyS0RsermkpIzAraMiT6kPwkpBSaizfk+4U17BwZj/POB trvo8y9HnfiY9MxGURMMTIokxAPOFaJrlOlQKzC032gB0poXE2WJqRLvq7XoBz7q SXhYLRquGSb4Wl9HJwMlO+o7P3/xImcJIzhqABhR6TtbNxwNi2hIMU= 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:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=VpaiJAGcfQV8eTdGuJwaiT6oPYc=; b=ai82gHY/+xDixkLfKAIB t7tSTPojC+rW9zh4kTnh08NvuOR20GIUfeH0hzI2HmQYRwypTi70mwPs3ah22abE ff9jYRJAG0EMQAOgnzVZ4vYZ/7hD/KHOhL0H3f90ukTKsyvbC/ekOinVkbt0OWwq XPEx+UDxQh5FjEPsU6EAg/A= Received: (qmail 26473 invoked by alias); 3 Apr 2013 13:38:30 -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 26447 invoked by uid 89); 3 Apr 2013 13:38:30 -0000 X-Spam-SWARE-Status: No, score=-6.7 required=5.0 tests=AWL, BAYES_00, KHOP_RCVD_UNTRUST, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD autolearn=ham version=3.3.1 Received: from cantor2.suse.de (HELO mx2.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Wed, 03 Apr 2013 13:38:28 +0000 Received: from relay1.suse.de (unknown [195.135.220.254]) by mx2.suse.de (Postfix) with ESMTP id 086CBA51B7 for ; Wed, 3 Apr 2013 15:38:26 +0200 (CEST) Date: Wed, 3 Apr 2013 15:38:25 +0200 (CEST) From: Richard Biener To: gcc-patches@gcc.gnu.org Subject: [PATCH] Fix PR56817 Message-ID: User-Agent: Alpine 2.00 (LNX 1167 2008-08-23) MIME-Version: 1.0 This fixes PR56817 - when unrolling a loop we may not process to outer loops of that loop without updating SSA form inbetween. The following patch arranges for that by defering outer loop processing to the next unrolling iteration. Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk and branch. Richard. 2013-04-03 Richard Biener PR tree-optimization/56817 * tree-ssa-loop-ivcanon.c (tree_unroll_loops_completely): Split out ... (tree_unroll_loops_completely_1): ... new function to manually walk the loop tree, properly defering outer loops of unrolled loops to later iterations. * g++.dg/torture/pr56817.C: New testcase. Index: gcc/tree-ssa-loop-ivcanon.c =================================================================== --- gcc/tree-ssa-loop-ivcanon.c (revision 197397) +++ gcc/tree-ssa-loop-ivcanon.c (working copy) @@ -1097,6 +1097,63 @@ propagate_constants_for_unrolling (basic } } +/* Process loops from innermost to outer, stopping at the innermost + loop we unrolled. */ + +static bool +tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer, + vec& father_stack, + struct loop *loop) +{ + struct loop *loop_father; + bool changed = false; + struct loop *inner; + enum unroll_level ul; + + /* Process inner loops first. */ + for (inner = loop->inner; inner != NULL; inner = inner->next) + changed |= tree_unroll_loops_completely_1 (may_increase_size, + unroll_outer, father_stack, + inner); + + /* If we changed an inner loop we cannot process outer loops in this + iteration because SSA form is not up-to-date. Continue with + siblings of outer loops instead. */ + if (changed) + return true; + + /* Try to unroll this loop. */ + loop_father = loop_outer (loop); + if (!loop_father) + return false; + + if (may_increase_size && optimize_loop_nest_for_speed_p (loop) + /* Unroll outermost loops only if asked to do so or they do + not cause code growth. */ + && (unroll_outer || loop_outer (loop_father))) + ul = UL_ALL; + else + ul = UL_NO_GROWTH; + + if (canonicalize_loop_induction_variables + (loop, false, ul, !flag_tree_loop_ivcanon)) + { + /* If we'll continue unrolling, we need to propagate constants + within the new basic blocks to fold away induction variable + computations; otherwise, the size might blow up before the + iteration is complete and the IR eventually cleaned up. */ + if (loop_outer (loop_father) && !loop_father->aux) + { + father_stack.safe_push (loop_father); + loop_father->aux = loop_father; + } + + return true; + } + + return false; +} + /* Unroll LOOPS completely if they iterate just few times. Unless MAY_INCREASE_SIZE is true, perform the unrolling only if the size of the code does not increase. */ @@ -1105,10 +1162,7 @@ unsigned int tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer) { vec father_stack; - loop_iterator li; - struct loop *loop; bool changed; - enum unroll_level ul; int iteration = 0; bool irred_invalidated = false; @@ -1124,34 +1178,9 @@ tree_unroll_loops_completely (bool may_i free_numbers_of_iterations_estimates (); estimate_numbers_of_iterations (); - FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST) - { - struct loop *loop_father = loop_outer (loop); - - if (may_increase_size && optimize_loop_nest_for_speed_p (loop) - /* Unroll outermost loops only if asked to do so or they do - not cause code growth. */ - && (unroll_outer || loop_outer (loop_father))) - ul = UL_ALL; - else - ul = UL_NO_GROWTH; - - if (canonicalize_loop_induction_variables - (loop, false, ul, !flag_tree_loop_ivcanon)) - { - changed = true; - /* If we'll continue unrolling, we need to propagate constants - within the new basic blocks to fold away induction variable - computations; otherwise, the size might blow up before the - iteration is complete and the IR eventually cleaned up. */ - if (loop_outer (loop_father) && !loop_father->aux) - { - father_stack.safe_push (loop_father); - loop_father->aux = loop_father; - } - } - } - + changed = tree_unroll_loops_completely_1 (may_increase_size, + unroll_outer, father_stack, + current_loops->tree_root); if (changed) { struct loop **iter; Index: gcc/testsuite/g++.dg/torture/pr56817.C =================================================================== --- gcc/testsuite/g++.dg/torture/pr56817.C (revision 0) +++ gcc/testsuite/g++.dg/torture/pr56817.C (working copy) @@ -0,0 +1,38 @@ +// { dg-do compile } +// { dg-options "--param max-unroll-times=32" } + +struct A {}; +A **q; +struct B +{ + A **j; + B () { j = q; } + A *& operator[] (unsigned long x) { return j[x]; } +}; +struct C +{ + C (int r) : v (), s (r) {} + A *& operator () (int i, int j) { return v[i * s + j]; } + B v; + int s; +}; +struct D +{ + D () + { + unsigned h = 2; + for (int i = 0; i < 1; ++i, h *= 2) + { + C w (h); + for (unsigned j = 0; j < h; ++j) + for (unsigned k = 0; k < h; ++k) + w (j, k) = new A; + } + } +}; +void +foo () +{ + for (int i = 0; i < 3; i++) + A (), A (), D (); +}