From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 25471 invoked by alias); 20 Aug 2009 12:49:23 -0000 Received: (qmail 25462 invoked by uid 22791); 20 Aug 2009 12:49:23 -0000 X-SWARE-Spam-Status: No, hits=-2.1 required=5.0 tests=AWL,BAYES_00 X-Spam-Check-By: sourceware.org Received: from mail1-relais-roc.national.inria.fr (HELO mail1-relais-roc.national.inria.fr) (192.134.164.82) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Thu, 20 Aug 2009 12:49:15 +0000 Received: from gaia.futurs.inria.fr (HELO [195.83.212.216]) ([195.83.212.216]) by mail1-relais-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 20 Aug 2009 14:49:11 +0200 Message-ID: <4A8D4647.1030909@inria.fr> Date: Thu, 20 Aug 2009 13:34:00 -0000 From: Albert Cohen User-Agent: Mozilla-Thunderbird 2.0.0.19 (X11/20090103) MIME-Version: 1.0 To: Richard Guenther CC: gcc@gcc.gnu.org Subject: Re: complete_unrolli / complete_unroll References: <4A8BE7B2.7080708@inria.fr> <84fc9c000908190507x708772cdueb8193a0ff7517aa@mail.gmail.com> <4A8BFF5F.5070708@inria.fr> <4A8C0405.9030008@inria.fr> <84fc9c000908190656p7ec6cc4aja93ff860a5f61960@mail.gmail.com> <84fc9c000908190658k23a13034s64cac8be7b2de827@mail.gmail.com> <4A8CA4BC.4020807@inria.fr> <84fc9c000908200148p57979f3cp5e440f778b8fc484@mail.gmail.com> In-Reply-To: <84fc9c000908200148p57979f3cp5e440f778b8fc484@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-IsSubscribed: yes Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org X-SW-Source: 2009-08/txt/msg00368.txt.bz2 Richard Guenther wrote: >> If this is not clear, I can write some pseudo-code to clarify :-). > > Can't we use graphite to re-roll loops? That is, compress the > polyhedron by introducing a new parameter? But maybe I am > not good at guessing what your initial bloat issue looks like. > > The reason I'm asking is that there is enough code out in the > wild that has loops with manually unrolled bodies - I have seen > up to 16 times here. > I agree that the conditions I propose are not as reliable as unrolling and checking if it helps. At some point, this kind of sandboxing of the IR to explore a tree of optimizations would be interesting... except for compilation time and memory usage :-( Great for iterative and machine learning optimization anyway. Regarding your rerolling question, it is currently not known. There is indeed a nice parallel between rerolling and the code generation algorithms in CLooG. But this is only for rerolling right after unrolling. The real problem is rerolling after a sequence of optimizations that took advantage of prior unrolling. In this case, we have an algorithm equivalence problem, very general and very nasty. Polyhedral approaches do help but so far did not do much more than very theoretical papers and toy prototypes (I can give references if you are interested). Clearly, it would be nice to have a rerolling pass, it would also help the intra-block vectorization (there are specific papers on this, and preliminary support in the vectorizer), but it is not something people understand well. We'll wait a little, but more feedback on conditions to stricten the application of the early unrolling pass will be helpful, then one of the Graphite developers may gets his or her hand dirty on it. Albert