Friday, July 08, 2005

Scaling up

I spent most of today debugging silly problems, that started to appear as I was feeding the compiler with larger examples. In a codebase of about 5000 lines simple things can become hard to find. It looks like I found the last of them, as I can't find a smallish 'list' example that doesn't work anymore. For example, an extended version of the example in my previous posting, now with 15 allocation sites and several functions (ident, dupl, makel) nicely converges to these 2 object contours:

1: ImmutableSet([])
2: ImmutableSet([class int_])
3: ImmutableSet([class float_])
4: ImmutableSet([])
5: ImmutableSet([])
unused [4, 5, 1]

As can be seen, in total 5 intermediate object contours are created, as the compiler splits and merges contours during each iteration. Although some steps of the iterative analysis as I've implemented it are slow (for example, by checking whether a tuple of tuples is in some Set), the theoretical complexity of the whole is greatly reduced, as CPA will create a boatload less templates when there are fewer object contours!

My next step will be to clean this stuff up some more, e.g. remove unused contours after each iteration, fix the fact that '[x]' is not supported, and start looking at other classes than list. At some point I will also have to start looking at nested and recursive types, and start thinking about termination issues.. shudder!!

No comments: