The verifier must create what is commonly known a "use-def chains" for
the bytecodes in a method, to determine which results from one
bytecode can flow as inputs to another bytecode ("data flow"). The
traditional way to do this (and the one used in most verifiers) is to
literally construct chains -- lots of little objects chained together
into lists. This is space consuming and time-consuming to do.
A different way to do it is with bitsets, where one bit in the set
represents one possible result from one bytecode. One bitset
represents the values set at any point in the program, and others
represent the values "killed" by the program flow. These can be
accumulated for basic blocks (whereas use-def chains are generally
done on a per-instruction basis) and fairly simple bit masking
operations can then be used to perform the global data flow analysis
that's needed for verification.
(Morel and Renvoise produced what's probably the best explanation of
this technique in http://doi.acm.org/10.1145/359060.359069 )
Of course, in the general case the bitsets can get too large, but
there are techniques for compressing them that reduce bitset size by a
factor of ten or more, and make even the largest Java method easily
tractable with this approach. (Though this technique I'll likely take
to my grave, since no one else is interested in it.)
On Oct 4, 6:32 pm, fadden <fad...@android.com> wrote:
> On Oct 4, 1:45 pm, DanH <danhi...@ieee.org> wrote:
>
> > Reference chains are slow and take up too much space.
>
> I don't know what you mean by "reference chains". Could you point out
> where in the code they're being used?
--
You received this message because you are subscribed to the Google
Groups "Android Developers" group.
To post to this group, send email to android-developers@googlegroups.com
To unsubscribe from this group, send email to
android-developers+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/android-developers?hl=en
