Re: [Sbcl-devel] A way to make control compiler (Nikodemus Siivola)

[Rob M. <ra...@ri...>]

Unfortunately lifetime analysis isn't optional, because it's used for 
register allocation.   I doubt your use of special variables is a 
contributing factor (unless sbcl generates significantly different code 
than CMUCL in this case.)    If it isn't a bug, then it more like has to 
do with the size and complexity of your flow graph (the number of 
conditionals and the branching structure) and the total amount of code 
in the function (especially variables that are live across conditional 
branches.)   The algorithm used could likely exhibit a N^2 blowup in 
space or time for some combinations of flow graph and variable 
lifetimes.  This usually isn't an issue for small functions, partly 
because of the use of bit-vectors operations, which are approximately 
constant time for hundreds of bits.

It is suggestive of something that it's blowing up inside 
lifetime-post-pass, since in some sense that isn't really the hard part 
of what's going on.    It makes me wonder if the problem is not that 
your flow graph is complex, but rather that you have a really big block 
that uses the same variables over and over again, since lifetime 
analysis splits blocks that are large (in terms of variables) to avoid 
N^2 blowup.   If you could get us more specific information about what 
function it's in when it's hanging, it's possible that a fairly simple 
algorithmic improvement could fix your problem.

   Rob