[llvm-dev] IR liveness analysis in 2019

[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


On Thu, Mar 7, 2019 at 8:13 PM Quentin Colombet <qcolombet at apple.com> wrote:

> Hi,
>
> On Mar 6, 2019, at 9:58 AM, Son Tuan VU via llvm-dev <
> llvm-dev at 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-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190307/8c51a0c4/attachment.html>