Initial implementation of liveness analysis

[gigiblender]

This PR is an initial implementation of liveness analysis for Relax programs and is based on the manifest_lifetimes pass in RelayVM.

It should handle nested control-flow in the form of if/else statements. At the moment, it does not support:

1. Aliasing in the form of VarBinding(Var, Var), MatchShape(Var, Var)
2. Tuples

The limitations are also mentioned here

[gigiblender]

cc @mbaret @YuchenJin @mikepapadim @areusch

[slyubomirsky]

FYI, I think you should be checking for calls to ExternFuncs because their results could also alias (well also, a call to an ordinary Function could alias its arguments). I think it might be easier to whitelist things that you can be certain will not alias another value (creating a constant, calling an op that creates a value, if-else where both branches are not aliasing), as there are many ways to alias: e.g., create a tuple containing a var, then index into that tuple.

Also, ordinary VarBindings also create aliases. I mention this because you put the aliasing todos only on MatchShape nodes, but both kinds of bindings can alias.

Yes, aliasing is a headache :sweat_smile:

[tqchen]

Note that some of the alias dependencies are managed by ref counting.

So if the purpose is to insert the kill op(which decref and does not do direct memory free), it is fine to ignore alias in such analysis. The catch is that such analysis result only being used to insert the early kill point.

For other cases such as memory sharing, then we should make sure that allocated tensor do not alias, in this case, restricting things onto special set of ops makes sense.

[slyubomirsky]

Yes, some values cannot be tracked statically and should be refcounted or otherwise garbage-collected. If we are going to have an analysis to track when values can be statically deallocated, we would need to be very certain that other references to it don't exist.