From owner-freebsd-hackers@FreeBSD.ORG Thu Nov 27 22:22:25 2008 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 88EBD1065675 for ; Thu, 27 Nov 2008 22:22:25 +0000 (UTC) (envelope-from christoph.mallon@gmx.de) Received: from mail.gmx.net (mail.gmx.net [213.165.64.20]) by mx1.freebsd.org (Postfix) with SMTP id E83AA8FC12 for ; Thu, 27 Nov 2008 22:22:24 +0000 (UTC) (envelope-from christoph.mallon@gmx.de) Received: (qmail invoked by alias); 27 Nov 2008 22:22:23 -0000 Received: from p54A3F275.dip.t-dialin.net (EHLO tron.homeunix.org) [84.163.242.117] by mail.gmx.net (mp051) with SMTP; 27 Nov 2008 23:22:23 +0100 X-Authenticated: #1673122 X-Provags-ID: V01U2FsdGVkX1+3eQJBSt239ZPFYl1dvjVkLgX1Ax7FJV0jLRH8fV eF/hpy0hYAQtoY Message-ID: <492F1D9E.9040607@gmx.de> Date: Thu, 27 Nov 2008 23:22:22 +0100 From: Christoph Mallon User-Agent: Thunderbird 2.0.0.18 (X11/20081124) MIME-Version: 1.0 To: Eygene Ryabinkin References: <492F0591.7050807@gmx.de> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-15; format=flowed Content-Transfer-Encoding: 7bit X-Y-GMX-Trusted: 0 X-FuHaFi: 0.55 Cc: freebsd-hackers@freebsd.org Subject: Re: New C compiler and analyzer lang/cparser in ports X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 27 Nov 2008 22:22:25 -0000 Eygene Ryabinkin schrieb: > Christoph, good day. > > Thu, Nov 27, 2008 at 09:39:45PM +0100, Christoph Mallon wrote: >> A few days ago libFIRM[1] and cparser were added to the ports tree. If >> you want to see, what other compilers besides GCC have to offer, this >> might be of interest for you. libFIRM is a modern optimizing >> intermediate representation (IR) library. cparser is a C compiler >> providing many useful warnings and uses libFIRM for optimization and >> code generation. > [...] > > The whole description looks like that of LLVM GCC port, http://llvm.org/ > Do you know something about that project and if yes, could you, please, > provide brief comparison of these two? Both LLVM and FIRM use SSA as an important aspect of their IR. FIRM uses it more extensively in backend. The whole FIRM backend operates on program graphs in SSA form. Spilling and register allocation are decoupled: First spilling is done and after that registers are allocated. There are several spilling algorithms available. The best so far is one based on the idea of Belady's algorithm and it produces very good results. Our novel approach to register allocation and copy coalescing was developed as PhD thesis by Sebastian hack. LLVM uses a more classical approach. It has a combined register allocation and spilling phase using a modified linear scan algorithm. LLVM not only needs an instruction schedule, but also a block schedule. FIRM does block scheduling after register allocation is done. The SSA based spilling of FIRM leads to better code (i.e. less spill and reloads) in most cases. A paper by Matthias Braun and Sebastian Hack submitted to the next CC elaborates on this subject. In the middle end both systems are quite similar, but there are some notable differences. LLVM uses instructions scheduled in basic blocks whereas FIRM resembles the "sea of nodes" proposed by Click and has no schedule in the "middleend". Actually a schedule is introduced after instruction selection. This is necessary, so spilling and register allocation can operator. To be more precise our representation is called an "explicit dependency graph": All necessary dependencies (we use dependencies, not (data) flow) are modelled as edges in the program graph. We use no temporary variables, but every node in the graph represents a value. If a node produces several results, projection nodes are used to get the different aspects. Memory is modelled as SSA value, too. You can have a look at this in our online demo of the compiler. The link is on our website. You can also read a bit more about FIRM there, too. You mentioned LLVM GCC. FIRM only has a stale GCC frontend, which is not maintained anymore. Currently there are three frontends available: C and Java using the Edison Design Group frontend and our own C frontend called "cparser". The latter is probably the more interesting option for you. Did you find the frontend examples interesting or are you mainly interested in optimization and backend aspects? Regards Christoph