Re: Help with Live Range Analysis?

John Carney wrote:


> I am working on a microcode project where register allocation is done
> by the programmer. There is nothing which prevents the programmer from
> allocating two or more variables to the same register and then
> inadvertently writing code with overlapping live ranges for those
> variables. The microcode assembler trusts the register allocation and
> this results in (numerous) bugs which are difficult to find.


After thinking myself, and reading the various replies, I'm not really
sure what you want to find out. Is it the content (variable-alias) of
the registers at any place in your code? Your sample code is not very
instructive, where does it reference variables, where registers? Or do
you have only 1 register, that's used implicitly by "read" and
"write"? What about other (computational...) instructions?


In my decompilers I had to implement an algorithm to find out, where
temporary variables live only in registers, not in memory, and where
temporary results are stored in memory or in the stack. I did this by
following the def-use chains of the involved resources (registers, CPU
flags) in strictly sequential code (Basic Blocks). The usage of (and
changes to) the registers and flags is described in a table, for every
machine instruction [a function can be used to decode register and
addressing modes in certain instructions]. The result is a set
(bitfield) of the register/flag resources, one for the required input
(use), and one for the output (def), for every statement. Then the
required resources at the begin, and the changed resources at the end
of the BB can be computed in a single run through every BB. Next comes
the analysis of the dependencies amongst the BB's, depending on what
shall be found out. Another array may be helpful, describing the
contents of the resources at the end of every BB (copy of a variable,
fixed value, expression, unchanged...), also depending on the desired
goal of the analysis. In your case it might be helpful to remember the
exact variable (or none), which will be found in a register at the end
of every BB. A stack trace instead may not be required in your
(microcode) case.


DoDi

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