From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 39D6ABC88 for ; Tue, 8 Feb 2005 19:32:27 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j18IWQEE026469 for ; Tue, 8 Feb 2005 19:32:26 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA00423 for ; Tue, 8 Feb 2005 19:32:26 +0100 (MET) Received: from qrnik.knm.org.pl (paf87.warszawa.sdi.tpnet.pl [217.96.225.87]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j18IWPdH023725 (version=TLSv1/SSLv3 cipher=EDH-RSA-DES-CBC3-SHA bits=168 verify=NO) for ; Tue, 8 Feb 2005 19:32:26 +0100 Received: from qrczak by qrnik.knm.org.pl with local (Exim 3.36 #1) id 1Cya9w-000607-00 for caml-list@inria.fr; Tue, 08 Feb 2005 19:32:24 +0100 To: caml-list@inria.fr Subject: Re: [Caml-list] paralell assignment problem X-Face: OW>RV&gN+&b-aiNY|U)f=S%w+/rK!);f>/W9IXg})]&F>ht.1Up8@04+_!gOp(_/l_-+E^. 2\vI)1=D,%HWiq)r(M/V~dr^5T^KF/[w5YZ4<0Sus3+O>l3uA/&W_21m?.s,Po8{pb0@ References: <1107832025.13571.260.camel@pelican.wigram> <87r7jrrp56.fsf@qrnik.zagroda> <1107885305.5022.211.camel@pelican.wigram> From: "Marcin 'Qrczak' Kowalczyk" Mail-Followup-To: caml-list@inria.fr Date: Tue, 08 Feb 2005 19:32:24 +0100 In-Reply-To: <1107885305.5022.211.camel@pelican.wigram> (skaller@users.sourceforge.net's message of "09 Feb 2005 04:55:06 +1100") Message-ID: <87ekfqkimf.fsf@qrnik.zagroda> User-Agent: Gnus/5.1006 (Gnus v5.10.6) Emacs/21.3 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Sender: "Marcin 'Qrczak' Kowalczyk" X-Miltered: at concorde with ID 420905BA.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 420905B9.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 sourceforge:01 elif:01 sequences:01 transformed:01 compiler:01 gcc:01 constants:01 writes:01 expression:01 tail:01 tail:01 ack:01 ack:01 int:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO autolearn=disabled version=3.0.2 X-Spam-Level: skaller writes: > fun ack(x:int,y:int):int => > if x == 0 then y + 1 > elif y == 0 then ack(x-1, 1) > else ack(x-1, ack(x, y-1)) > endif > ; > > No temporaries are needed in either tail call, > and either order of assignment will work. > But my actual code created 2 temporaries for each > tail call, unnecessarily. In the implementation of my language Kogut which targets C, on the level I assign argument values to parameter slots (global variables), expressions have already been processed into sequences of statements, such that the remaining expressions contain only variables, constants, and simple operations which don't call unknown code, don't have side effects, don't depend on the time when they are evaluated, and can actually be transformed into C expressions, not C statements. On this level it's clear what expressions depend on which virtual registers. I don't bother with finding the optimal assignment - I just make an easy choice way which generates quite good result in most cases: Positions are generally assigned in order. For each position, if the target of the assignment is used among later source expressions, then a C temporary is introduced and the temporary is assigned from the source expression; otherwise the target is assigned directly (unless it's the same as the source, in which case the assignment is skipped). At the end all temporaries are assigned to their targets. Sometimes this generates more temporaries than would be possible with a different order, but I don't care. The C compiler must still introduce a temporary register for moving between two global variables, so maybe it would generate the same code even if all values were passed through temporaries; I've heard gcc is pretty good in propagating copies. -- __("< Marcin Kowalczyk \__/ qrczak@knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/