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: Re: wip-cse Date: Mon, 16 Apr 2012 15:56:58 -0700 Message-ID: <87sjg31e11.fsf@pobox.com> References: <87bomr30xz.fsf@pobox.com> <874nsjuzok.fsf@gnu.org> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: dough.gmane.org 1334617036 28079 80.91.229.3 (16 Apr 2012 22:57:16 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Mon, 16 Apr 2012 22:57:16 +0000 (UTC) Cc: guile-devel@gnu.org To: ludo@gnu.org (Ludovic =?utf-8?Q?Court=C3=A8s?=) Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Tue Apr 17 00:57:15 2012 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 1SJurB-00069U-1P for guile-devel@m.gmane.org; Tue, 17 Apr 2012 00:57:13 +0200 Original-Received: from localhost ([::1]:54802 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SJurA-0004Rf-EM for guile-devel@m.gmane.org; Mon, 16 Apr 2012 18:57:12 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:48524) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SJur6-0004Qy-V1 for guile-devel@gnu.org; Mon, 16 Apr 2012 18:57:10 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1SJur4-0007Yi-Ln for guile-devel@gnu.org; Mon, 16 Apr 2012 18:57:08 -0400 Original-Received: from a-pb-sasl-sd.pobox.com ([74.115.168.62]:54233 helo=sasl.smtp.pobox.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1SJur4-0007XJ-Cj; Mon, 16 Apr 2012 18:57:06 -0400 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-sd.pobox.com (Postfix) with ESMTP id 8965A9419; Mon, 16 Apr 2012 18:57:02 -0400 (EDT) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type:content-transfer-encoding; s=sasl; bh=JHIjph2zvO2t HWFSiueWY/lVxNo=; b=EWMqr5gToGWIXruZAHolXZGFG/JIvG/1qPNCZYzJ5ssq tXRDDuGGoGY/buP2QFsX3RwSQyl8uJknBATU/Fh/d1SJOMooKvyYbhY57vVk2A1A f6nD524UhiR2jCYWQ+Xd/lkjt7MYHFxR1bOuK7UAoBLQRjfzcgfuwL6JioMKi90= DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=from:to:cc :subject:references:date:in-reply-to:message-id:mime-version :content-type:content-transfer-encoding; q=dns; s=sasl; b=mao5S3 9J72E0ILbeTuRhdXGoxD638mMHxILLEQ0vRArcpgQuG0SjJiQWPOeVqhJ+h4VeG2 viz7139+BiirXRkdO/FtgB8aRL+GoDrkvEEQ3kGimcbC+EW7NjccMre2jE5NM2mf AcLtUxpkemdW7vkFYfH9seRw0YXNdaA2MnKp4= 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 8113F9418; Mon, 16 Apr 2012 18:57:02 -0400 (EDT) Original-Received: from badger (unknown [67.180.176.231]) (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 C7DB99417; Mon, 16 Apr 2012 18:57:01 -0400 (EDT) In-Reply-To: <874nsjuzok.fsf@gnu.org> ("Ludovic =?utf-8?Q?Court=C3=A8s=22'?= =?utf-8?Q?s?= message of "Mon, 16 Apr 2012 23:36:27 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.4 (gnu/linux) X-Pobox-Relay-ID: 7A8893F0-8817-11E1-BE88-B1B0728A0A4D-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:14278 Archived-At: On Mon 16 Apr 2012 14:36, ludo@gnu.org (Ludovic Court=C3=A8s) writes: > Initially, I was expecting things like: > > (f (* a b) (* a b)) > =3D> > (let ((x (* a b))) > (f x x)) > > but AIUI the CSE pass here eliminates duplicate references when they are > superfluous, but not when they are needed as above, right? This pass does a few related things: * Replacement of an expression with a reference to a lexical identifier. * Inferring the boolean value of an expression, given previous expressions that were true. * Eliminating an expression where it can cause no effect. It does not name new values, however. If we switched to CPS as our IR, then we would have a lot more names, and CSE could be more effective. >> I'm attaching a log of the things that it folds in a normal Guile >> build. > > I=E2=80=99m not sure what the messages mean. Could you explain? Sure. In these I just replaced some of the calls to "log" with "pk". The "inferring" lines indicate boolean-valued expressions that were folded. The "elided" lines indicate useless expressions in effect context. The "propagate-value" lines... hm, there aren't any. They would correspond to replacing expressions with lexical-refs. That's a bug probably, caused by the switch to vhashes, I would imagine. I'll take a look. >> I'm pretty happy with it, except for the speed. > > What impact does it have on compilation time in module/? Dunno. It almost doubles the fresh recompilation of of peval, though (1.3s to 2.3s). > >> seeing that lookup in vhashes is fairly slow. Dunno. If we can speed >> up vhashes somehow then we win in CSE, peval, and other passes, so >> probably it's best to focus there. > > I think we=E2=80=99ll need C-level profiling to see what=E2=80=99s going = on. Do you > have such info already? Otherwise I can look into it. I don't have any such info yet. > Also, a bit of CSE could help: ;-) Hmm :) If I had to guess, it would be: > scheme@(ice-9 vlist)> ,optimize (%vhash-assoc key vhash eq? hashq) > $3 =3D (begin > (define khash > (let ((size (vector-ref > (let ((s vhash)) > (if (eq? (struct-vtable s) ) > (struct-ref s 0) > ((@@ (srfi srfi-9) throw) > 'wrong-type-arg > 'vlist-base > "Wrong type argument: ~S" > (list s) > (list s)))) > 3))) > (and (> size 0) (hashq key size)))) ^ Here we see a call to hashq. Guile doesn't recognize that it's a pure function (depending on &mutable-data, causing &type-error), so it assumes that it could mutate a toplevel variable, causing future checks not to fold. (Because a future access to does not commute with a call to `hashq'.) Also "vhash" is a toplevel ref. If it were lexically bound, I think things would be a little bit different. Dunno! Regards, Andy --=20 http://wingolog.org/