| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
In the process I'm starting to realize that my approach to avoiding spills
isn't ideal. It works for local variables but not to avoid spilling outputs.
To correctly decide whether to spill to an output register or not, we really
need to analyze when a variable is live. If we don't do that, we'll end
up in one of two bad situations:
a) Don't spill the outermost use of an output register (or just the outermost
scope in a function). This is weird because it's hard to explain to the
programmer why they can overwrite a local with an output above a '{' but
not below.
b) Disallow overwriting entirely. This is easier to communicate but quite
inconvenient. It's nice to be able to use eax for some temporary purpose
before overwriting it with the final result of a function.
If we instead track liveness, things are convenient and also easier to
explain. If a temporary is used after the output has been written that's
an obvious problem: "you clobbered the output". (It seems more reasonable
to disallow multiple live ranges for the output. Once an output is written
it can only be shadowed in a nested block.)
That's the bad news. Now for some good news:
One lovely property Mu the language has at the moment is that live ranges
are guaranteed to be linear segments of code. We don't need to analyze
loop-carried dependences. This means that we can decide whether a variable
is live purely by scanning later statements for its use. (Defining 'register
use' is slightly non-trivial; primitives must somehow specify when they
read their output register.)
So we don't actually need to worry about a loop reading a register with
one type and writing to another type at the end of an iteration. The only
way that can happen is if the write at the end was to a local variable,
and we're guaranteeing that local variables will be reclaimed at the end
of the iteration.
So, the sequence of tasks:
a) compute register liveness
b1) verify that all register variables used at any point in a program
are always the topmost use of that register.
b2) decide whether to spill/shadow, clobber or flag an error.
There's still the open question of where to attach liveness state. It can't
be on a var, because liveness varies by use of the var. It can't be on a
statement because we may want to know the liveness of variables not referenced
in a given statement. Conceptually we want a matrix of locals x stmts (flattened).
But I think it's simpler than that. We just want to know liveness at the
time of variable declarations. A new register variable can be in one of
three states w.r.t. its previous definition: either it's shadowing it,
or it can clobber it, or there's a conflict and we need to raise an error.
I think we can compute this information for each variable definition by
an analysis similar to existing ones, maintaining a stack of variable definitions.
The major difference is that we don't pop variables when a block ends.
Details to be worked out. But when we do I hope to get these pending tests
passing.
|
| |
|
|
|
| |
The second var to the same register in a block doesn't need to spill. We're
never going to restore the var it's shadowing.
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
| |
This is a lot of code for a single test, and it took a long time to get
my data model just right. But the test coverage seems ok because it feels
mostly like straight-line code. We'll see.
I've also had to add a lot of prints. We really need app-level trace generation
pretty urgently. That requires deciding how to turn it on/off from the
commandline. And I've been reluctant to start relying on the hairy interface
that is POSIX open().
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| |
|
|
| |
Test for 'index'.
|
| |
|
|
|
|
|
|
|
|
|
|
|
| |
And we're using it now in factorial.mu!
In the process I had to fix a couple of bugs in pointer dereferencing.
There are still some limitations:
a) Indexing by a literal doesn't work yet.
b) Only arrays of ints supported so far.
Looking ahead, I'm not sure how I can support indexing arrays by non-literals
(variables in registers) unless the element size is a power of 2.
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| | |
|
| |
|
|
|
| |
This was initially disquieting; was I writing enough tests? Then I noticed
I had TODOs for some missing checks.
|
| |
|
|
|
| |
This is a particularly large abstraction leak: SubX arrays track their
lengths in bytes, and therefore Mu as well.
|
| |
|
|
| |
Forgot to actually use the new type-dispatch in commit 6017.
|
| | |
|
| |
|
|
| |
Some deduplication, though this may be a premature abstraction.
|
| |
|
|
|
|
|
|
| |
I'd been thinking I didn't need unconditional `break` instructions, but
I just realized that non-local unconditional breaks have a use. Stop over-thinking
this, just support everything.
The code is quite duplicated.
|
| |
|
|
|
|
|
|
|
|
|
|
| |
We'll be doing type-checking in a separate phase in future. For now we
need only to distinguish between literals and non-literals for x86 primitive
instructions.
I was tempted to support x86 set__ instructions for this change:
https://c9x.me/x86/html/file_module_x86_id_288.html
That will happen at some point. And I'll simplify a bunch of branches for
results of predicate functions when it happens.
|
| | |
|
| | |
|
| | |
|
| |
|
|
|
|
|
|
|
| |
This cleans up a bunch of little warts that had historically accumulated
because of my bull-headedness in not designing a grammar up front. Let's
see if the lack of a grammar comes up again.
We now require that there be no space in variable declarations between
the name and the colon separating it from its type.
|
| |
|
|
|
|
|
|
| |
Allow comments at the end of all kinds of statements.
To do this I replaced all calls to next-word with next-mu-token.. except
one. I'm not seeing any bugs yet, any places where comments break things.
But this exception makes me nervous.
|
| |
|
|
|
|
|
|
| |
Support calling SubX code from Mu. I have _zero_ idea how to make this
safe.
Now we can start writing tests. We can't use commandline args yet. That
requires support for kernel strings.
|
| | |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
I've been saying that we can convert this:
{
var x: int
break-if-=
...
}
..into this:
{
68/push 0/imm32
{
0f 84/jump-if-= break/disp32
...
}
81 0/subop/add %esp 4/imm32
}
All subsequent instructions go into a nested block, so that they can be
easily skipped without skipping the stack cleanup.
However, I've been growing aware that this is a special case. Most of the
time we can't use this trick:
for loops
for non-local breaks
for non-local loops
In most cases we need to figure out all the intervening variables on the
stack and emit code to clean them up.
And now it turns out even for local breaks like above, the trick doesn't
work. Consider what happens when there's a loop later in the block:
{
var x: int
break-if-=
...
}
If we emitted a nested block for the break, the local loop would become
non-local. So we replace one kind of state with another.
Easiest course of action is to just emit the exact same cleanup code for
all conditional branches.
|
| |
|
|
|
|
|
| |
Turns out we can't handle them like conditional loops.
This function to emit cleanup code for jumps is getting quite terrible.
I don't yet know what subsidiary abstractions it needs.
|
| | |
|
| |
|
|
|
| |
Now that we have the infrastructure for emitting cleanup blocks, the labeled
variants should be easy as well.
|