Re: Stack based-Register Based

> IOW: I claim that if our VM has 256 registers, our ISA has 32
> registers and our expression has 300 concurrent temporary values, the
> high level language can schedule the block down to 256 registers by
> adding stores and loads as appropriate. These stores and loads should
> not hinder the JIT or load-time compiler from also being able to
> generate an optimized register scheduling. In fact, the stores and
> loads added in should be ones that would have been added in anyhow if
> the compiler were optimizing directly from the 300 values to the 32
> values in a single step.
>
> I don't, however know if this is true. Anyone out there able to offer a
> better proof either way?


That would be nice, wouldn't it? Let's suppose that your optimisers
are 'associative' (there is probably an "official" term for this but I
don't know what it is)...


By 'associative optimiser' I mean an optimiser which transforms
semantically equivalent programs A and B into equivalently "good"
programs A' and B'. Note that A' and B' need not be the same, just
equivalently good under whatever criteria for optimisation are
desired.


If all your optimisers are associative, then your assertion must be
true since they must, pretty much by definition, leave semantics
unchanged.


Notice that an ideal optimiser *must* be associative. Given
semantically equivalent programs A and B, it must always produce
equivalently good code A' and B'. So if your optimisers are ideal,
your assertion is true.


However, I don't know that provably optimal (or even associative)
optimisers exist. But my limited knowledge on this subject leads me to
believe that most scheduling and register allocation algorithms use
heuristics of some sort (esp in the JIT case). If this is the case,
the quality of the output will almost certainly depend on the input,
even if the semantics are unchanged.


All the best


Jonathan

Return to the comp.compilers page.
Search the comp.compilers archives again.