[llvm-dev] IR liveness analysis in 2019

[Son Tuan VU via llvm-dev]

Hello,

I found this thread back in 2014 [1] . Does anyone know if there has been any attempt to answer this request?

To clarify, I am looking for an analysis that computes the textbook definition of variable liveness: "given a SSA value V and a point P, is there a possible path from P to any use of V?" which is equivalent to "is V live at point P?"

I can write something myself (and will if need be), but just want to avoid reinventing the wheels in case improvements have been made since 2014. If not, what's the best way to contribute this analysis to LLVM? I mean, for example, is "Computing Liveness Sets for SSA" by Boissinot  [2] efficient enough to be implemented in LLVM? Or should I find a better algorithm to solve this?

[1] http://lists.llvm.org/pipermail/llvm-dev/2014-July/074793.html

[2] http://hal.inria.fr/docs/00/58/53/03/PDF/RR-7503.pdf

Thanks for your help,

Cheers

Son Tuan Vu

[Quentin Colombet via llvm-dev]

Hi,

On Mar 6, 2019, at 9:58 AM, Son Tuan VU via llvm-dev <llvm...@lists.llvm.org> wrote:

Hello,

I found this thread back in 2014 [1] . Does anyone know if there has been any attempt to answer this request?

To clarify, I am looking for an analysis that computes the textbook definition of variable liveness: "given a SSA value V and a point P, is there a possible path from P to any use of V?" which is equivalent to "is V live at point P?"

I can write something myself (and will if need be), but just want to avoid reinventing the wheels in case improvements have been made since 2014. If not, what's the best way to contribute this analysis to LLVM? I mean, for example, is "Computing Liveness Sets for SSA" by Boissinot  [2] efficient enough to be implemented in LLVM?

This one should be efficient enough.

That said, what are you trying to achieve?

The reason we don’t have such algorithm in LLVM IR is because we don’t need it. Usually def-uses chains and dominance property are enough for what the optimizers want to do.

Or should I find a better algorithm to solve this?

[1] http://lists.llvm.org/pipermail/llvm-dev/2014-July/074793.html

[2] http://hal.inria.fr/docs/00/58/53/03/PDF/RR-7503.pdf

Thanks for your help,

Cheers

Son Tuan Vu

_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

[Son Tuan VU via llvm-dev]

Hi Quentin,

Well what I'm trying to do is that, given a (maybe really big) set of particular points Pi, find out all the SSA variables Vi that are live at these points (i.e. def(Vi) dom Pi and at least one use(Vi) is reachable from Pi). The problem with classic def-use chains and dominance property is that I have to do this query for each point Pi and each variable Vi, which does not scale for big programs or for big set of particular points.

Cheers,

Son Tuan Vu

[Quentin Colombet via llvm-dev]

On Mar 7, 2019, at 2:01 PM, Son Tuan VU <sontua...@gmail.com> wrote:

Hi Quentin,

Well what I'm trying to do is that, given a (maybe really big) set of particular points Pi, find out all the SSA variables Vi that are live at these points (i.e. def(Vi) dom Pi and at least one use(Vi) is reachable from Pi).

That sounds like answering a liveness query indeed, but what do you do with this information?

[Jeremy Morse via llvm-dev]

Hi,

I may have a use-case for IR liveness analysis, although it's in the
context of debuginfo. Using the sample code from this bug report [0],
which is a fairly trivial loop:

int foo(int count) {
int result = 0;
for (unsigned long long ix = start; ix != count; ++ix)
result += external(ix);
return result;
}

On x86_64 the 32-bit "count" comparison to 64 bit "ix" necessitates
sign extension of "count". That sign extension gets hoisted out of the
loop, the original value of "count" goes out of liveness, and the
produced debuginfo has no variable location for "count" across the
loop body. I can generate similar examples involving the movement of
pointer bitcasts that lead to pointer variables getting lost.

We can easily generate variable location expressions to recover the
value of "count" from the sign-extended value, so that "count" has a
location across the loop, but (I believe) we'd need a liveness
analysis to determine where & when in the IR to generate such
locations. (Debuginfo of course has to "cope" with things going out of
liveness, whereas liveness has to preserve the functioning of
everything else in IR).

[0] https://bugs.llvm.org/show_bug.cgi?id=38997

--
Thanks,
Jeremy

[Quentin Colombet via llvm-dev]

Thanks Jeremy for the use case!

I have a hard time to see how that would work in practice.

Essentially, in your example, you have to detect that count went out of liveness, so that means we need to somehow maintain the original liveness of the program to do that comparison and that’s where I don’t see how we can do that.
Also, ultimately IIUC we want to mark the extended count value as being count, but it seems to me that this is as hard if not harder to teach the optimization how to propagate this information in the first place instead of analyzing the liveness difference.

[Son Tuan VU via llvm-dev]

Hello all,

Thanks for your replies.

Indeed, I do not really know how to solve Jeremy's use case. My use case is much simpler, I only want to have a list of variables that are live at an interesting point and insert a new instruction that consumes the live variable at that point.

So do you think that people do want a liveness analysis at the IR level?

Son Tuan Vu