Re: Help with Live Range Analysis?

> label_1:
> write a;
> write b;
>
> label_2:
> read a;
> write c;
>
> nway_branch label_3 label_5 label_8;
>
> label_3:


I don't know of any tools that would do it for you, but it would be
pretty easy to hack something up yourself. You basically have use/def
(=read/write) information and the flow graph. You can write a data-
flow analysis that will calculate live-in and live-out sets for each.
Then, just walk each basic block, computing the "current live" set,
and looking for when a def (read) interferes with what's currently-
live.


There is a pretty decent explanation of how to construct live-in/live-
out here:
http://www.cs.cornell.edu/courses/cs412/2001sp/lectures/lec25.pdf


Once you have the live-out sets for each basic block, computing
interferences is easy. For each basic block bb, keep a set, live-now.
Then, walk backwards over each instruction, noting interferences and
updating live-now. The algorithm is as follows:


live-now = live-out(bb)
for ins in bb, backwards:
        for def in defs(ins):
                for reg in live-now:
                        mark-interference(def, reg)
        for def in defs(ins):
                set-del(def, live-now)
        for use in uses(ins):
                set-add(use, live-now)


Where the functions defs(ins) and uses(ins) give the registers written
and read, respectively, by each instruction.

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