[LLVMdev] Asserts in bundleWithPred() and bundleWithSucc()

[Andrew Trick]

On Feb 5, 2013, at 8:18 AM, Sergei Larin <slarin at codeaurora.org> wrote:

> Jakob,
> 
>  Consider a counterexample. In a late pass I speculatively move
> instructions between BBs to improve code density and handle some peculiar
> back end specific situations which could not be handled in earlier passes. I
> move instructions one at a time. Currently I do it in a worklist fashion - I
> collect several possible candidates, and then actually move one. Some moves
> are _speculative_. Next move after that is totally dependent on up-to-date
> liveness information. If/when we decide to do proper _global_ instruction
> scheduling, we will need this mechanism to perform flawlessly.
>  On a low level, if I start with a correct set of live-ins, I can do
> _incremental_ liveness update pretty much always (I do skip some nasty
> corner cases for parallel semantics). My current problem is that I had to
> implement this whole incremental liveness analysis in my late pass...
> (because LIS does not work that late)... which is something I do not want to
> carry forward for too long if I can avoid it.
> 
>  In short, I do need a version of "move instruction" (or handleMove) that
> would produce accurate global liveness after its use. If 
> 
> LIS.beginChanges(); // change // LIS.endChanges();
> 
> will work as fast and efficiently, no problem then, but I have this feeling
> that incremental liveness update (when possible) will be easier and cheaper
> than full scan.

The liveness update Jakob described could also be used for efficient incremental update. In fact, we can keep the handleMove API as a convenient wrapper. LiveIntervals simply needs to know which instruction moved.

The more general API provides flexibility for clients that may perform a sequence of steps where the intermediate   liveness is either inconsistent or inefficient to compute. It would also provide a way to recompute liveness after a pass which can be extremely useful for debugging and verification.

Regarding global liveness. If you only care about extended basic blocks that are sequentially numbered, then I don't think we should talk about global liveness update, which is a different problem altogether. Handling extended basic blocks would make the API messy but should be just as efficient as local liveness. The only difference is that some of your intervals won't end at uses.

-Andy