I have an idea roughly what's happening, but i need to work through
it with the lurkers to pinpoint the problem. So ..
First, Felix eliminates unused variables, and that's essential,
rather than an optimisation. For example:
var windows_version = winver();
var linux_version = linver();
var osx_version = osxver();
...
println$ osx_version;
In this program I am running OSX, so this will work.
If you're running Linux the program will stuff up, because
the function "osxver()" won't work on Linux. This is what we
want.
So clearly, windows_version and linux_version must be eliminated
to get rid of their initialisers, otherwise if that stuff is in the library
then NO program will work!
Here's another example:
var thread_pool = create_thread_pool();
// not used
I'm not using the thread_pool so we want to eliminate the variable
to get rid of the creator.
Second. Felix does the elimination with a very poor algorithm.
It collects all the used symbols, and copies them to a new
symbol table. So if you have
var a = 1;
var b = a;
var c = b;
and c is not used, c is eliminated. But b is used so it is kept.
So Felix does the symbol garbage collection AGAIN.
This time b is eliminated but a is kept. So Felix does the
garbage collection AGAIN. This time a is eliminated.
Felix then does the collection AGAIN. This time nothing
is eliminated so it's finished. This is extremely inefficient,
because it's done globally over the whole program, and it's
done after a large number of optimisations (i.e. not just
once!). The algorithm could be made more efficient: one pass
would be enough, if one recognized the "result" expressions:
the return values of a function, for example, or any value
output, and used them as "roots".
In any case, complete elimination of unused variables is essential.
Note carefully assigning the result of a generator with side effects
to an unused variable WILL eliminate the variable and the generator
invocation! It's not a bug! It's MEANT to do that!
Third. Now the nitty gritty, problem number ONE.
What's "use" mean????
In theory this is simple. It means the variable is read.
If the variable is a structure, then we can make do with any
part being read (it would be better to eliminate unread parts
but that's tricky!)
This means in a simple assignment:
a = b
then b is used but a is not. Writing isn't use.
What about read/modify;wr9te:
++i;
Nope. That's not a use because the value is only read for the purpose
of writing a different value. however here:
x = i++
variable i is used. So now consider this:
a . i . mem = 1
here, i is used because it is read. Only a is written (mem is a field name
so it isn't a variable). Usually, everything on the LHS of an assignment is
"used" except the "top level lvalue". Of course this is a little tricky because
its actually nested:
get (get (a, i), mem)
so we would have to carefully analyse the LHS of an assignment to find
all the non-lvalues.
But remember "in principle" Felix doesn't have any assignments.
It uses pointers instead,. So if we do
(&x) <- a
we have to decide x is not used. But this is bad because
var px = &x;
px <- a;
Here px is used, it's read to calculate where to store a. So we have to decide
x i used as well, even though it is only addressed, not read. Once we have
a pointer to a variable, we don't know how the pointer is going to be used,
so if the pointer is used at all, the variable has to be considered used.
[In general, aliasing etc means the alternative is data flow analysis]
So in general, if the address is taken in the LHS of a <- operator,
that's NOT a use, provided its the "innermost" pointer. For example:
(&x) . (*&y) <- 1
here y is used! But x is not.
I suspect Felix is getting this wrong, but I'm not sure.
At present the code says: the LHS is not checked for
usage if it's a simple variable or a projection BEXPR_get_n.
[That handles tuple indices, and maybe some arrays,
and I suspect record and struct components too]
In the array case, with a integer variable index I think it's
forgetting to consider the index as being used.
The result is an exception being thrown and a hack in the
compiler just eliminated the whole assignment: the hack
is to allow just "deleting" unused variables. The hack shouldn't
be needed now that horrible inefficient symbol garbage collector
is being used. So that's possible error 1, though I'm not confident
because I know the index variables i,j using in nbody are counted
as used anyhow (they're used on the RHS too)
Now for the NEXT problem. Lazy evaluation.
Felix can replace a variable with its value.
It does this even for projections. For example
var x = 1,2;
var y = x.0;
var z = x.1;
may well produce:
var y = (1,2).0;
var z = (1,2).1;
In this case, that would lead to
y = 1;
z = 2;
which is nice. However, here:
var a = 1,1,1,1,1 .... 1; // 1000 times
for i in 0 upto 900 do
print a.i, a.(i+1) .... a. (i+99); // 100 times
done
it would be a disaster because you'd get 100 copies of
the 1000 values.
But that's just slowness. The real disaster would be if
Felix did this kind of substitution on the LHS of an assignment:
a . i = 1;
WOOPS! If we replace a with a value here we'd be "addressing
an rvalue" on the assignment and the modification would just
get lost.
However, again this only applied to the "lvalue" variable.
It's possible this is the bug too.
OK, so why not eliminate assignments altogether?
After all I've been trying to do that for some time.
Well, there's a reason. Consider:
var x = expr;
If we do:
var x : typeof(expr);
set (&x, expr);
and "set" is an arbitrary procedure, we cannot use the value
of x in place of x (because we don't know that it is "expr").
If we use an intrinsic
&x <- expr
we can special case it. Note that vals are often represented
by variables too, however the initial assignment is given by
BEXPR_init, not BEXPR_assign. Of course we could use
assignment for vals (just because the user can't take the address
doesn't mean the compiler can't :)
SO there we have it. Two possible sources of the bug:
(a) failing to count something as used that should be
(b) replacing an lvalue by its initial value in an assignment
I really can't think of anything else. I do know, it is NOT assigning
the value.
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
Free Next-Gen Firewall Hardware Offer
Buy your Sophos next-gen firewall before the end March 2013
and get the hardware for free! Learn more.
http://p.sf.net/sfu/sophos-d2d-feb
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
