From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Andy Wingo Newsgroups: gmane.lisp.guile.devel Subject: peval update Date: Wed, 28 Sep 2011 20:03:33 +0200 Message-ID: <87ehz0wnm2.fsf@pobox.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: dough.gmane.org 1317233030 25014 80.91.229.12 (28 Sep 2011 18:03:50 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Wed, 28 Sep 2011 18:03:50 +0000 (UTC) To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Wed Sep 28 20:03:45 2011 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1R8yTw-0006MO-9o for guile-devel@m.gmane.org; Wed, 28 Sep 2011 20:03:44 +0200 Original-Received: from localhost ([::1]:45980 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R8yTv-0007wY-QR for guile-devel@m.gmane.org; Wed, 28 Sep 2011 14:03:43 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:55507) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R8yTs-0007wT-EG for guile-devel@gnu.org; Wed, 28 Sep 2011 14:03:41 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1R8yTr-0003CC-1k for guile-devel@gnu.org; Wed, 28 Sep 2011 14:03:40 -0400 Original-Received: from a-pb-sasl-sd.pobox.com ([74.115.168.62]:54712 helo=sasl.smtp.pobox.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1R8yTq-0003C7-VI for guile-devel@gnu.org; Wed, 28 Sep 2011 14:03:39 -0400 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id 4C5D47654 for ; Wed, 28 Sep 2011 14:03:38 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to :subject:date:message-id:mime-version:content-type; s=sasl; bh=w +8BCl7biV6JlZvC4tajta+6e5Q=; b=tv3LSxvOlMnD7UF/AgjIx2R4+kQppMLt8 oB0XemmuuQxI8Xr03q7arJHDwre3PqHdfRCMNx2pk6AYbtlw5slHEHnas8A7QDq5 g7DO9meZ1agsNr2gAwRmbUeWkNwvwpc21zHIwYyEDIx8a6Ki1s3flj4Tn2qJf8s/ KtVLl3NURA= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:subject :date:message-id:mime-version:content-type; q=dns; s=sasl; b=BUa oGlGNB/l38d0qVp+M0LVfHhA+MHp5wbqmh5OnVhJ0ptWPMAk7Rxn72kpksI5hxsy ZuSC5Pn2JXoriTvWRd2xldIDtowlFUSB3drXkIALCz1yWbH1qXjK1rfKOp8roaaG a+XM/1WrgMYiIvJ8ozG481YHioZq2FFtKP8hC3Ys= Original-Received: from a-pb-sasl-sd.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id 457E77653 for ; Wed, 28 Sep 2011 14:03:38 -0400 (EDT) Original-Received: from badger (unknown [91.117.99.155]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTPSA id A3B8C7652 for ; Wed, 28 Sep 2011 14:03:37 -0400 (EDT) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) X-Pobox-Relay-ID: 30A0D1B2-E9FC-11E0-9176-65B1DE995924-02397024!a-pb-sasl-sd.pobox.com X-detected-operating-system: by eggs.gnu.org: Solaris 10 (beta) X-Received-From: 74.115.168.62 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:12810 Archived-At: Hi! I was hacking on peval recently, and wanted to give an update. Firstly, it now works on all of Guile's code -- all of its constructs. It's pretty careful to not reorder effects, though there could be bugs of course. Also it can be used for some simple (sub-0CFA) analysis to prove that, for example, a prompt tag is unreferenced and so a prompt can be removed. This is important for the `while' case, that if no `break' or `continue' clause is found, no prompt is residualized. Also, peval is now strictly O(N), because it has "effort counters", as in Waddell and Dybvig's paper. Each call site in the source program is allocated some amount of "effort", and if that effort is all used up, peval aborts back to the inlining attempt and residualizes the call. N call sites * constant effort = O(N). Peval also has size counters, to control code growth, but they are not currently used. Instead there are some heuristics. We should fix this. Another thing to fix is that peval doesn't always spend its effort wisely. It can visit operands more than once, which is counter-productive. It should memoize residual code emitted, as Waddell and Dybvig do. If it did this residualization at time of use instead of time of definition, that would turn the algorithm into being demand-driven, allowing more accurate code size computations. It would also allow context-specific processing of operands to calls, like in test context or effect context. Demand-driven processing would also make `letrec' optimization more effective. Currently `letrec'-bound bindings are not mutually inlined. You can see the result of this in psyntax-pp.scm: things that are inlined in the body are not inlined in the letrec-bound helpers. That's really all the TODOs that I have, though I'm not sure when to get to them. Thanks a lot to Ludovic for producing such a lucid bit of code! Andy -- http://wingolog.org/