Re: [abc] type assigner complexity in Soot

    hendren> Pavel (one of the abc'ers) is trying to speed up the
    hendren> type assigner in Soot because as John previously
    hendren> noted, the algorithm does not scale well when there
    hendren> are a large number of local variables.
             .
             .
             .
    hendren> Could you John and Etienne read his comments below
    hendren> (I have edited them slightly) and answer if you know
    hendren> if there is a reason why the sets could not be
    hendren> updated in place, and if the alternate data
    hendren> structure could work.

I simply don't understand the typing algorithms well enough to
provide an informed opinion. The one caution I would make is
probably already obvious to anybody who has looked at the typing
code: everything is complicated by the use of ecr() ("equivalence
class representative" if I remember correctly) to implement fast
set unions.

It took me this long just to say "I don't know" because I have
been attempting to inform my opinion by looking again at my old
kludge of keeping the parents and children in sorted lists, so
duplicate elimination doesn't require temporary Sets. I added a
check that the lists really are sorted (because other merges
might change their keys). The kludge reduced the time to process
abc.aspectj.parse.CUP$Grm$actions on my machine from 5 min 29 sec
to 1 min 16 sec, and the resulting class file was identical.
However, I have only tested the kludge on one other class, and
the code is UGLY UGLY UGLY.

I need to devote my limited soot time to finishing up changes to
ThrowableSet that I said I was going to commit 3 weeks ago
(unanticipated complications in ExceptionalBlockGraph). So I have
put copies of my modified
soot/jimple/toolkits/typing/TypeVariable.java and
soot/jimple/toolkits/typing/integer/TypeVariable.java into
http://www.sable.mcgill.ca/~jjorge1/typing-merge-kludge.jar
in case nobody finds the time to do anything more clever with the
typing data structures.

I emphasize that these files are not ready to be committed to
Soot as is. At the very least, all the common code in the two
files should be factored out (I just copied and pasted from one
to the other to save thinking of the proper way to write methods
that would accept either soot.jimple.toolkits.typing.TypeVariable
or soot.jimple.toolkits.typing.integer.TypeVariable as
parameters). If you do contemplate using the kludge, I think it
would be a good idea for somebody other than me to do the
cleanup, since it would insure that another set of eyes look at
the code before it goes into Soot: I don't understand the typing
algorithms well enough to have any confidence I haven't broken
them.

It would probably be a better idea yet to perform a fundamental
overhaul of the typing data structures, but I suspect that may be
too big a job to manage before the next release date.
Received on Tue Sep 21 14:12:32 2004