From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Noah Lavine Newsgroups: gmane.lisp.guile.devel Subject: Re: CPS and RTL Date: Thu, 24 Jan 2013 08:50:17 -0500 Message-ID: References: <87libjhtk4.fsf@pobox.com> <878v7jnd5m.fsf@tines.lan> <878v7ij2bk.fsf@pobox.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=f46d042f949a4d6a2404d40917dd X-Trace: ger.gmane.org 1359035438 487 80.91.229.3 (24 Jan 2013 13:50:38 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 24 Jan 2013 13:50:38 +0000 (UTC) Cc: Andy Wingo , Mark H Weaver , guile-devel To: Nala Ginrut Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Thu Jan 24 14:50:56 2013 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1TyNCh-0005q5-2t for guile-devel@m.gmane.org; Thu, 24 Jan 2013 14:50:55 +0100 Original-Received: from localhost ([::1]:44729 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TyNCP-00039x-Lq for guile-devel@m.gmane.org; Thu, 24 Jan 2013 08:50:37 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:48439) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TyNCI-00039c-Ki for guile-devel@gnu.org; Thu, 24 Jan 2013 08:50:34 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TyNC7-0005Zs-AY for guile-devel@gnu.org; Thu, 24 Jan 2013 08:50:30 -0500 Original-Received: from mail-da0-f43.google.com ([209.85.210.43]:44457) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TyNC7-0005ZA-0p for guile-devel@gnu.org; Thu, 24 Jan 2013 08:50:19 -0500 Original-Received: by mail-da0-f43.google.com with SMTP id u36so4285454dak.30 for ; Thu, 24 Jan 2013 05:50:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:x-received:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type; bh=E5xOXJKVWHlnkZ/mwJHOgBhNO1PUb/GsWsUrJC3NoOI=; b=ZeTEABDx2jEsRP7c6cyfhokfsng2ibRXjWuik2bTrhhR+KUbv7rboeFKk6kS0dXtoP 1BEzo5aUoHp9NOsLINfoBzh4CUYhvX24eQdUyUtsRjgJC0fLehzITfELIVVmbBsEW1ga WHJcK0lLkUO17c3M0q8fvu6muSX61ejlKEgvHelRHoLQ+FxtSe4S/Et4vyn+dKELxwjb clyMDDfR7hdVrF9U8PKck3BKPHIqzwh+iEIruDFq1K0uhDG0hmGpz28AcfBAtUVTET7V Wiyvx/0fs/Sz0KUe7uNFzYzPv7yHeUnT6dtqOeug1+HVF1dJ5NpeFbB7Dr4hYcmK3gm4 xh5w== X-Received: by 10.66.73.164 with SMTP id m4mr4908286pav.12.1359035417585; Thu, 24 Jan 2013 05:50:17 -0800 (PST) Original-Received: by 10.68.242.73 with HTTP; Thu, 24 Jan 2013 05:50:17 -0800 (PST) In-Reply-To: X-Google-Sender-Auth: zls9t9GCPZkMY9L0St-wyS2d_5w X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x [fuzzy] X-Received-From: 209.85.210.43 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:15580 Archived-At: --f46d042f949a4d6a2404d40917dd Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Hello Andy and Mark, Thanks for the review! There has actually been more progress since I pushed that branch. I hit a point in the CPS->RTL stuff where I had trouble because I didn't know how to do things (like mutable variables) in RTL. So I've actually ported the compiler to GLIL in a branch on my computer. I also have a working Tree-IL->CPS compiler for some of Tree-IL (it's not done yet). I thought that might be a better way forward because CPS and RTL are, to a certain extent, separate ideas. I'll push my wip-cps branch, which contains a Tree-IL->CPS compiler and a CPS->GLIL compiler. What I'm working on now is actually how to represent mutable variables in CPS. I think having explicit environment structures would be nice (and fit with Kennedy's paper), but I haven't figured out the details yet. I realize it might be confusing to start with CPS->RTL, then switch to CPS->GLIL, then switch back later when the RTL branch is ready. If you'd rather do it that way, we can skip the CPS->GLIL phase. Some thoughts: * Yes, passes might be good. I had thought of writing some generic control-flow operators like 'compute-fixpoint' and then writing other things in terms of those. * Using tree-il first sounds good to me. * I also think that CPS should have some construct which says 'do these things in any order'. I haven't put one in yet, mostly because the compiler wouldn't take advantage of it anyway. Noah On Thu, Jan 24, 2013 at 5:38 AM, Nala Ginrut wrote: > Are you guys going to use CSP to implement SSA for AOT? > =E5=9C=A8 2013-1-24 PM6:36=EF=BC=8C"Andy Wingo" =E5=86= =99=E9=81=93=EF=BC=9A > > Hi! >> >> On Thu 24 Jan 2013 10:28, Mark H Weaver writes: >> >> > The problem is that CPS fixes the order in which everything is >> > evaluated, such as the order in which procedure arguments are >> > evaluated, the order in which 'let' or 'letrec' initializers are >> > evaluated, etc. The fact that these orders are unspecified in the >> > direct-style gives the compiler freedom to choose an order that >> > generates the best code, and apparently this freedom can often result >> > in significant gains. Such ordering decisions must be made before the >> > conversion to CPS. >> >> Agreed with the sentiment; however, two points: >> >> * we can have a CPS with let / letrec / * operators that bind a number >> of values in unspecified order, and have a pass later that fixes >> their order. >> >> * code motion passes like CSE depend on effects analysis, and can >> often commute some operations >> >> Anyway, violent agreement! >> >> Cheers, >> >> Andy >> -- >> http://wingolog.org/ >> >> --f46d042f949a4d6a2404d40917dd Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Hello Andy and Mark,

Thanks for the rev= iew! There has actually been more progress since I pushed that branch. I hi= t a point in the CPS->RTL stuff where I had trouble because I didn't= know how to do things (like mutable variables) in RTL. So I've actuall= y ported the compiler to GLIL in a branch on my computer. I also have a wor= king Tree-IL->CPS compiler for some of Tree-IL (it's not done yet).<= /div>

I thought that might be a better way forward beca= use CPS and RTL are, to a certain extent, separate ideas. I'll push my = wip-cps branch, which contains a Tree-IL->CPS compiler and a CPS->GLI= L compiler. What I'm working on now is actually how to represent mutabl= e variables in CPS. I think having explicit environment structures would be= nice (and fit with Kennedy's paper), but I haven't figured out the= details yet.

I realize it might be confusing to start wi= th CPS->RTL, then switch to CPS->GLIL, then switch back later when th= e RTL branch is ready. If you'd rather do it that way, we can skip the = CPS->GLIL phase.

Some thoughts:

* Yes, pa= sses might be good. I had thought of writing some generic control-flow oper= ators like 'compute-fixpoint' and then writing other things in term= s of those.

* Using tree-il first sounds good to me.

* I also think that CPS should have some= construct which says 'do these things in any order'. I haven't= put one in yet, mostly because the compiler wouldn't take advantage of= it anyway.

Noah
=

On Thu, Jan 24, 2013 at 5:38 AM, Nala Gi= nrut <nalaginrut@gmail.com> wrote:

Are you guys going to use CSP= to implement SSA for AOT?

=E5=9C=A8 2013-1-24 PM6:36=EF=BC=8C"Andy Wi= ngo" <wingo@po= box.com>=E5=86=99=E9=81=93=EF=BC=9A

Hi!

On Thu 24 Jan 2013 10:28, Mark H Weaver <mhw@netris.org> writes:

> The problem is that CPS fixes the order in which everything is
> evaluated, such as the order in which procedure arguments are
> evaluated, the order in which 'let' or 'letrec' initia= lizers are
> evaluated, etc. =C2=A0The fact that these orders are unspecified in th= e
> direct-style gives the compiler freedom to choose an order that
> generates the best code, and apparently this freedom can often result<= br> > in significant gains. =C2=A0Such ordering decisions must be made befor= e the
> conversion to CPS.

Agreed with the sentiment; however, two points:

=C2=A0 * we can have a CPS with let / letrec / * operators that bind a numb= er
=C2=A0 =C2=A0 of values in unspecified order, and have a pass later that fi= xes
=C2=A0 =C2=A0 their order.

=C2=A0 * code motion passes like CSE depend on effects analysis, and can =C2=A0 =C2=A0 often commute some operations

Anyway, violent agreement!

Cheers,

Andy
--
http://wingolog.org/=


--f46d042f949a4d6a2404d40917dd--