On Thu, 2006-08-24 at 09:49 -0700, Erick Tryzelaar wrote:
> skaller wrote:
> I really think that something like this would be the simplest solution.
Err.. which of the 100 different ways to do it are you suggesting
is the simplest?
> And technically, wouldn't it decompose from this:
>
> proc f(x:int): int {
> return x + 1;
> }
>
> proc g(y:int): int {
> return y + 2;
> }
>
> val z = f(g(2));
>
> Into this:
>
> proc f(x:int) (px:int) {
> *px = x + 1;
> }
>
> proc g(y:int) (py:int) {
> *py = y + 2;
> }
>
> ref tmp1 = 2;
> f(2, tmp1);
>
> // the optimizer may be able to detect that we could substitute tmp2 for
> tmp1 here without breaking anything
> ref tmp2;
> g(tmp1, tmp2);
I don't think it will at the moment, but if we can formalise
the pattern, I can probably make it.
If you consider this code block:
t1 = x + y
t2 = t1 + z
t3 = t2 + k
return t3
you will note t1 is not used in the last assignment.
Assuming t1 and t3 are the same type, you could wite
t1 = t2 + k
return t1
instead, in other words alias t1 and t3.
The correct way to do this is to use a union.
BUT C++ DOES NOT ALLOW UNIONS OF CONSTRUCTABLE TYPES.
I am tempted to <flame></flame> here :)
Note that sometimes you can force the C compiler to do it,
by using automatic storage and block scope, but in general
this won't work (and it gets in the way of goto and other
constructions, plus we have the stupid jump past
initialisation rule, where a language with a lame type system
tries to enforce dynamic safety statically .. but doesn't
have the wherewithall to do it properly .. consequently
breaking dynamically safe usage gratuitously.
I am very tempted to make my next language generate native
code directly .. C gets in the way, C++ is much worse.
> This pattern, as you probably know, is a common in mathematic
> applications when you want to apply multiple matrix operations without
> creating multiple temporaries. Supporting this pattern directly in the
> syntax would be really quite useful, in my opinion :)
The one optimisation that IS done is tail-rec parallel assignment.
IN a tail recursive call:
fun f(x,y,z) ... return f(a,b,c)
which is optimised by
loop:> ... x,y,z = a,b,c; goto loop;
the tuple assignment is done in parallel semantically,
meaning this works:
x,y,z = x+1, y-1, z+y+x;
To do that, you do:
t1 = x+1; t2 = y-1; t3 = z+y+x;
x = t1; y = t2; z = t3;
which uses 3 temporaries. You do this to avoid modifying
a variable which is yet to have its old value used on the
RHS of the next assignment.
Felix reorders and unravels these assignments
to minimise the number of temporaries used.
The algorithm is NP-hard, and it doesn't always get
the minimum, but it usually does reasonably well.
In general what you're asking for is data flow analysis ..
and that's quite hard.
Specific patterns could be optimised however. The best
way to achieve this is to construct a test case which
is non-optimal, then suggest a pattern to detect which
can be used to optimise it, implement that, and check
the optimisation works for the test case.
--
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net
-------------------------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
_______________________________________________
Felix-language mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/felix-language
