From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Lynn Winebarger Newsgroups: gmane.emacs.devel Subject: Re: native compilation units Date: Mon, 20 Jun 2022 08:34:41 -0400 Message-ID: References: Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="000000000000bf8a5305e1e0544b" Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="30909"; mail-complaints-to="usenet@ciao.gmane.io" Cc: Andrea Corallo , emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Mon Jun 20 14:36:23 2022 Return-path: Envelope-to: ged-emacs-devel@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1o3Gdj-0007pl-3e for ged-emacs-devel@m.gmane-mx.org; Mon, 20 Jun 2022 14:36:23 +0200 Original-Received: from localhost ([::1]:32966 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1o3Gdh-0005z2-Fo for ged-emacs-devel@m.gmane-mx.org; Mon, 20 Jun 2022 08:36:21 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:60266) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1o3GcO-0004hp-17 for emacs-devel@gnu.org; Mon, 20 Jun 2022 08:35:00 -0400 Original-Received: from mail-oa1-x33.google.com ([2001:4860:4864:20::33]:43559) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1o3GcJ-0002bV-P5 for emacs-devel@gnu.org; Mon, 20 Jun 2022 08:34:58 -0400 Original-Received: by mail-oa1-x33.google.com with SMTP id 586e51a60fabf-fe023ab520so14025901fac.10 for ; Mon, 20 Jun 2022 05:34:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=RBpBfy0YSDSNYmAtOzIcCEBPBFuQ4p28UT0QaSwTT7c=; b=R5wjM8T+Q3emYLAQ1sTJUrwpnPcSXK2mj3DnKNj5CZhXowsFE1F/GF/zb8p4g/lSuO 2eH16+0vxNyAEtkY4l78rHHxvGNWXLhBzoaLSndfWi2xMh/FAFraqkV4/LjYw4nw1Rdj eK/FEIcMBCmYbZ7+tq7T1PM5KI7xzMQyHi8wuZvUEVsup4+Wq7pupELYELrSX7v33uzp 3XhnmKInhoRN9d+eJ600i+dkHg/JEzGulMCeiD9Ggp/VYUrLxxKDP8uBOLMbq81lJgpI 5twRDHWNXgKABZUbsnATrjX6+M8FxKDipM8nl3VSyxn6vLqk6kR2Wsj8lkcUIl+Qj+p3 LQ3A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=RBpBfy0YSDSNYmAtOzIcCEBPBFuQ4p28UT0QaSwTT7c=; b=GXzXAwcbA71npmNrE0lz14wbU74327XENydIVyr0o+Asu2GtAaxa6pZuYsTpnbPLQs qt7ZKhcJqazKb+SgStgdg++3Z4/2vSakxyqFzBQVCKDCwBX9yCYQg6FsybWrdL+8wsJU opEkFCQ5gPcBkkdI9/SvXHAEcbREnFDBqvVuMr5lG7scrRW03cHGA56kqU0FVxfAtf9+ F6tzH4E3NXcFb3FWxqX6/lCCGg2JuDeT9igsOVb8lb+ixcDmlAOeT3YB3rjJHoSiqxcJ DTuvb/IXzIFN+oQHuAs+Ci4jfKiaFIvZIHsdxB/FNP574RYzNJQlTxceAbihxqkl2dk0 cEnw== X-Gm-Message-State: AJIora/AyaxlLLqPO4zC1mpfUigl7a2z8Bd1O8ypeKWkokyaJSmKKUyz B1sfcTetWXC9dlHH+erldBH0HZkNHF6VOQ9OjT8= X-Google-Smtp-Source: AGRyM1uixv/s9l2B1mdKj/kti6mDZUOdOnZQk8Ak1t66pT5FLAlzz1elHYWI49uhKqfe1IJ0tE75pDiFJCU9uozCcY4= X-Received: by 2002:a05:6870:c1d1:b0:101:f706:bf29 with SMTP id i17-20020a056870c1d100b00101f706bf29mr2561778oad.247.1655728494314; Mon, 20 Jun 2022 05:34:54 -0700 (PDT) In-Reply-To: Received-SPF: pass client-ip=2001:4860:4864:20::33; envelope-from=owinebar@gmail.com; helo=mail-oa1-x33.google.com X-Spam_score_int: -20 X-Spam_score: -2.1 X-Spam_bar: -- X-Spam_report: (-2.1 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01 autolearn=ham autolearn_force=no X-Spam_action: no action X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane-mx.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.io gmane.emacs.devel:291465 Archived-At: --000000000000bf8a5305e1e0544b Content-Type: text/plain; charset="UTF-8" On Sun, Jun 19, 2022 at 9:39 PM Lynn Winebarger wrote: > On Sun, Jun 19, 2022 at 7:02 PM Stefan Monnier > wrote: > >> >> Proper tail recursion elimination would require changing the *normal* >> function call protocol. I suspect you're thinking of a smaller-scale > > version of it specifically tailored to self-recursion, kind of like >> what `named-let` provides. Note that such ad-hoc TCO tends to hit the >> same >> semantic issues as the -O3 optimization of the native compiler. >> E.g. in code like the following: >> >> (defun vc-foo-register (file) >> (when (some-hint-is-true) >> (load "vc-foo") >> (vc-foo-register file))) >> >> the final call to `vc-foo-register` is in tail position but is not >> a self call because loading `vc-foo` is expected to redefine >> `vc-foo-register` with the real implementation. >> >> I'm only talking about the steps that are required to allow the compiler > to > produce code that implements proper tail recursion. > With the abstract machine currently implemented by the byte-code VM, > the "call[n]" instructions will always be needed to call out according to > the C calling conventions. > The call[-absolute/relative] or [goto-absolute] instructions I suggested > *would be* used in the "normal" function-call protocol in place of the > current > funcall dispatch, at least to functions defined in lisp. > This is necessary but not sufficient for proper tail recursion. > To actually get proper tail recursion requires the compiler to use the > instructions > for implementing the appropriate function call protocol, especially if > "goto-absolute" is the instruction provided for changing the PC register. > Other instructions would have to be issued to manage the stack frame > explicitly if that were the route taken. Or, a more CISCish call-absolute > type of instruction could be used that would perform that stack frame > management implicitly. > EIther way, it's the compiler that has to determine whether a return > instruction following a control transfer can be safely eliminated or not. > If the "goto-absolute" instruction were used, the compiler would > have to decide whether the address following the "goto-absolute" > should be pushed in a new frame, or if it can be "pre-emptively > garbage collected" at compile time because it's a tail call. > > For the record, my point of reference for a classic implementation of efficient lexical closures and proper tail recursion is Clinger's TwoBit compiler for Larceny Scheme, and the associated "MacScheme" abstract machine: https://www.larcenists.org/twobit.html. That system is implemented in several variants. Each has a well-defined mapping of the state of the MacScheme machine state to the actual machine state for compiled code. That system does not have the constraint of having a byte-code interpreter and native-code implementation co-existing, but if they do coexist and are expected to be able to call each other with the "normal" (lisp, not C) calling conventions, defining the abstract machine state that has to be maintained between calls would be a key step. If calling between byte-code and native-code is expected to have the same overhead as calling between lisp and C, then I suppose that's not necessary. Lynn --000000000000bf8a5305e1e0544b Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Sun, Jun 19, 2022 at 9:39 PM Lynn Wine= barger <owinebar@gmail.com>= wrote:
On Sun, Jun 19, 2022 a= t 7:02 PM Stefan Monnier <monnier@iro.umontreal.ca> wrote:

Proper tail recursion elimination would require changing the *normal*
function call protocol.=C2=A0 I suspect you're thinking of a smaller-sc= ale
version of it specifically tailored to self-recursion, kind of like
what `named-let` provides.=C2=A0 Note that such ad-hoc TCO tends to hit the= same
semantic issues as the -O3 optimization of the native compiler.
E.g. in code like the following:

=C2=A0 =C2=A0 (defun vc-foo-register (file)
=C2=A0 =C2=A0 =C2=A0 (when (some-hint-is-true)
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (load "vc-foo")
=C2=A0 =C2=A0 =C2=A0 =C2=A0 (vc-foo-register file)))

the final call to `vc-foo-register` is in tail position but is not
a self call because loading `vc-foo` is expected to redefine
`vc-foo-register` with the real implementation.

I'm only talking about the steps that are require= d to allow the compiler to=C2=A0
produce code that implements pro= per tail recursion.
With the abstract machine currently implement= ed by the byte-code VM,
the "call[n]" instructions will= always be needed to call out according to
the C calling conventi= ons.
The call[-absolute/relative] or [goto-absolute] instructions= I suggested
*would be* used in the "normal" function-c= all protocol in place of the current
funcall dispatch, at least t= o functions defined in lisp.=C2=A0=C2=A0
This is necessary but no= t sufficient for proper tail recursion.
To actually get proper ta= il recursion requires the compiler to use the instructions
for im= plementing the appropriate function call protocol, especially if
= "goto-absolute" is the instruction provided for changing the PC r= egister.
Other instructions would have to be issued to manage the= stack frame
explicitly if that were the route taken.=C2=A0 Or,= =C2=A0 a more CISCish call-absolute
type of instruction could be = used that would perform that stack frame
management implicitly.
EIther way, it's the compiler that has to determine whether a = return
instruction following a control transfer can be safely eli= minated or not.
If the "goto-absolute" instruction were= used, the compiler would
have to decide whether the address foll= owing the "goto-absolute"
should be pushed in a new fra= me, or if it can be "pre-emptively
garbage collected"= =C2=A0 at compile time because it's a tail call.
=C2=A0
=

For the record, my point of re= ference for a classic implementation of efficient
lexical closure= s and proper tail recursion is Clinger's TwoBit compiler for
= Larceny Scheme, and the associated "MacScheme" abstract machine:<= /div>
https://www.la= rcenists.org/twobit.html.=C2=A0 =C2=A0That system is implemented
<= div>in several variants.=C2=A0 Each has a well-defined mapping of the state= of the
MacScheme machine state to the actual machine state for c= ompiled code.
That system does not have the constraint of having = a byte-code interpreter
and native-code implementation co-existin= g, but if they do coexist and=C2=A0
are expected to be able to ca= ll each other with the "normal" (lisp, not C)
calling c= onventions, defining the abstract machine state that has to be=C2=A0
<= div>maintained between calls would be a key step.
If calling betw= een byte-code and native-code is expected to have the same=C2=A0
= overhead as calling between lisp and C, then I suppose that's not neces= sary.

Lynn=C2=A0=C2=A0

<= /div> --000000000000bf8a5305e1e0544b--