Re: HLL expression -> ASM

"Ben L. Titzer" <>
31 Mar 2001 02:46:43 -0500

          From comp.compilers

Related articles
HLL expression -> ASM (Alexei A. Frounze) (2001-03-26)
Re: HLL expression -> ASM (Dan Bishop) (2001-03-27)
Re: HLL expression -> ASM (Alexei A. Frounze) (2001-03-31)
Re: HLL expression -> ASM (Ben L. Titzer) (2001-03-31)
Re: HLL expression -> ASM (Randall Hyde) (2001-03-31)
Re: HLL expression -> ASM (Marco van de Voort) (2001-04-04)
Re: HLL expression -> ASM (Alexei A. Frounze) (2001-04-10)
Re: HLL expression -> ASM (Bill A.) (2001-04-10)
Re: HLL expression -> ASM (2001-04-10)
| List of all articles for this month |

From: "Ben L. Titzer" <>
Newsgroups: comp.compilers
Date: 31 Mar 2001 02:46:43 -0500
Organization: Purdue University
References: 01-03-131 01-03-153
Keywords: parse, code
Posted-Date: 31 Mar 2001 02:46:42 EST

On 27 Mar 2001, Dan Bishop wrote:
> > I know how to parse the source, how to evaluate expressions several
> > similar ways: recursively or using stack(s). OK, that works perfectly,
> > no problems. And I can create a tree for the expression as well.
> >
> > Now, how do I transform the tree/whatever (let's say only integer
> > values/vars involved in the expression) into an ASM piece of code w/o
> > consuming extra memory for partial results, just using CPU registers?
> [If you pretend the registers are the stack and assign the "pushed"
> values to registers, you can get code that's not bad considering how
> easy this technique is. -John]

A more complicated technique but much more efficient is referred to as
"instruction tiling", where you basically traverse the tree and look
for the largest "tile" (instruction) that will fit over part of the
tree. For example:

VAL = MEM(ADD(base,offset))

can be tiled by one (x86) assembly instruction,

mov VAL.register, [base+offset]

If offset had been some more complicated expression, its code would be
emitted first, with its eventual result being stored in a register
that is passed up the tree. The pattern matching algorithm is pretty
straight forward. Basically you just determine whether one tree
matches a pattern by looking at the largest tiles first and doing a
sequence of IFs.

That would leave you with another problem though, one which you
probably will have to face at some point, however. That's register
allocation, and there exist fairly straightforward algorithms for
liveness analysis and register allocation.

Post a followup to this message

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