Yeah, I oversimplified the above description -- the verifier tracks (and must do so, in order to do valid verification) stack entry contents, which is equivalent to registers (assuming that Dalvik somehow tracks "spill" registers, which it must in order to do valid verification). Apparently Dalvik, like Sun, treats each bytecode as essentially a separate basic block, which is a valid way to do it -- there are pros and cons to having explicit basic blocks. The work list is a fairly standard way to iterate through the bytecodes/blocks (though in many cases reverse postorder is better -- my memory's a little fuzzy on the tradeoffs).
In the bitmap scheme each stack entry/register has several bits assigned, one for each possible type that could conceivably reach it. If an object pointer is assigned then all the bits for that class hierarchy are set, and when flows combine the bitsets are "anded" together. Thus the value that reaches a use automatically represents the classes valid at that point, taking into account the different flows. The same bitmap can also be used to track the "newness" of values (those that still need to be "constructed") and several other things. And of course in any dataflow scheme a degree of constant propagation falls out for free. On Oct 5, 1:05 pm, fadden <[email protected]> wrote: > On Oct 4, 5:09 pm, DanH <[email protected]> wrote: > > > 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. > > Ah. The current verifier just tracks the contents of each register > (Dalvik isn't Java, registers not stack), and uses a work-list > approach to figure out what to do next. Each register value is a > small enumeration (indicating a primitive type) or a Class reference. > > The verification process is also used to generate the register maps > for type-precise GC, which means it needs to store the register state > for every instruction that could be a GC point. (If it were just > about verification, it would only need to retain it for the start of > each basic block.) > > The current version doesn't really treat basic blocks in a fancy way; > it just has a bit flag on each instruction that indicates if it's a > branch target. This leads to some inefficiencies in the work-list > scan. A future version will identify the basic blocks, use a reverse > postorder traversal to reduce the number of times we have to process > the same stretch, and do backward flow analysis for live-precise > register maps. -- You received this message because you are subscribed to the Google Groups "Android Developers" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/android-developers?hl=en
