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: CPS common subexpression elimination landed Date: Mon, 07 Apr 2014 09:44:53 +0200 Message-ID: <87lhvhk2h6.fsf@pobox.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1396856723 17774 80.91.229.3 (7 Apr 2014 07:45:23 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 7 Apr 2014 07:45:23 +0000 (UTC) To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Mon Apr 07 09:45:19 2014 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 1WX4F2-0004Yp-MH for guile-devel@m.gmane.org; Mon, 07 Apr 2014 09:45:16 +0200 Original-Received: from localhost ([::1]:32814 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WX4F2-00024M-Bh for guile-devel@m.gmane.org; Mon, 07 Apr 2014 03:45:16 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:35246) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WX4Er-0001me-Uc for guile-devel@gnu.org; Mon, 07 Apr 2014 03:45:10 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WX4Ek-0004f9-CG for guile-devel@gnu.org; Mon, 07 Apr 2014 03:45:05 -0400 Original-Received: from a-pb-sasl-quonix.pobox.com ([208.72.237.25]:53843 helo=sasl.smtp.pobox.com) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WX4Ek-0004er-8o for guile-devel@gnu.org; Mon, 07 Apr 2014 03:44:58 -0400 Original-Received: from sasl.smtp.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 6DC5A10C31 for ; Mon, 7 Apr 2014 03:44:57 -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=X u9DPWbarYp5NSbtrLPCjfBn1GI=; b=lXmjQP3Goc5qhOt4r+6n5U6y1vqQAa+gv Yi3xpHKbuf4n6XqNk6WQOWRVKhJQdK+c3BhA6IULxNsfJJ/xVowKfZgBbj9mrsa7 zsdje7RoXsiSZ8uI7n1nXJc5LeoAaoYWxR3zFg0LA2eRyweYObMsSGC9pfE/JnYd EpHrzrkcRU= 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=SZf cflr7pgcwFAoFvJeugu6OnABjCHEsvWpmGq8ggAITCUZc2OQlq5FbCPZ3CG5hbrB 4/2kgFfXGAxAqWRBHSgb2ZoAZYUien8wviiG2ohUKKFm/tzwwlxzq/hXZeVyacWu 4f3FTNoEHmLVqT5BuuFH601bIcB//cEBvqi24WYs= Original-Received: from a-pb-sasl-quonix.pobox.com (unknown [127.0.0.1]) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTP id 6441110C2F for ; Mon, 7 Apr 2014 03:44:57 -0400 (EDT) Original-Received: from badger (unknown [88.160.190.192]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by a-pb-sasl-quonix.pobox.com (Postfix) with ESMTPSA id 4E0AD10C2E for ; Mon, 7 Apr 2014 03:44:56 -0400 (EDT) User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux) X-Pobox-Relay-ID: 8370C4D0-BE28-11E3-A3D6-873F0E5B5709-02397024!a-pb-sasl-quonix.pobox.com X-detected-operating-system: by eggs.gnu.org: Solaris 10 X-Received-From: 208.72.237.25 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:17040 Archived-At: Hi, Just a brief note to say that I've landed common subexpression elimination on the new CPS intermediate language on the master branch. It completely replaces the old pass over Tree-IL that I wrote about here: http://wingolog.org/archives/2012/05/14/doing-it-wrong-cse-in-guile The differences are these: 1. The new pass operates on CPS instead of Tree-IL, so it sees more eliminatable expressions. 2. The new pass uses a fixed-point data-flow analysis, avoiding bad complexity characteristics of the old implementation. 3. The new pass rewrites the tree to make the scope chain exactly reflect the dominator tree, so that all dominating expressions are eligible for CSE. See the notes from Stephen Weeks here: http://mlton.org/pipermail/mlton/2003-January/023054.html I didn't find the tree rewrite to be particulatly onerous; it's lines 490-498 in cse.scm. 4. Bailout is no longer modelled as an effect; instead a new pass runs that prunes control-flow joins after bailouts, because a primcall to `throw' will never rejoin control flow. 5. We still propagate truthy expressions, as the old pass does, so you can reduce (if a (if a 10 20) 30) to (if a 10 30). As a simple benchmark, consider changing module/language/cps/compile-bytecode.scm to default #:cse? to #f, and thereby bootstrap a Guile without CSE. Call that compiler A. A normal (with CSE) build would be compiler B. Now the test case would be compiling boot-9.scm with both compilers, with the option #:cse? #t. In this case compiler B is about 4% faster than compiler A. However, if we set #:cse? #f for compiler A, compiler A is faster -- so CSE doesn't really pay for itself yet at bootstrap time (though the new pass is still faster than the old pass). 4% is not very much, although this was just one test. However I think CSE is an important building block for future work, and it does speed up code, so I think we keep it on by default, as it was before. Compile-time overhead appears to be about 7 or 8% of compilation time. Regards, Andy -- http://wingolog.org/