Posted
about 13 hours
ago
by
tglek
I work on static analysis by lamp-light and proudly cycle wearing Firefox imagery by daylight. Today I was pleased to discover that the flyer for the Portland Century ride now prominently features the Firefox logo in one of the 4 photos. It’s also
... [More]
in the scrolling thing on the website =D
This picture was taken on one ride with the most firefox fans ever. On parts of the course, it felt like every 5 minutes someone was volunteering info on how awesome firefox is. [Less]
Posted
about 16 hours
ago
by
nor...@blogger.com (David Bolter)
Aaron Leventhal has started a thread called: "Mozilla accessibility -- collecting stories & dreams". If you'd like to read what folks say about the Mozilla Foundation and its relentless commitment to keeping the internet a place for everyone, check it out.
Posted
about 17 hours
ago
by
dmandelin
Tamarin (technically, tamarin-tracing, henceforth TT)-related projects keep peeking up at me from the horizon. First, there’s a good chance I’ll have an intern working on TT this summer. And then there’s this “Tracehydra” idea. It’s a way
... [More]
to connect Spidermonkey’s JS parser with the TT execution engine. This is the plan:
Where “profit” means “run Javascript really fast”. Tracehydra would be the fluffy cloud that translates Spidermonkey bytecode to Tamarin IL (or possibly LIR-the details get confusing fast). (In the interest of reducing confusion slightly, I’ll say that IL stands for intermediate language, and is roughly a synonym for bytecode. TT people often refer to their IL as “Forth” because they based the design on Forth or something, but I know nothing more about Forth than that it involves stacks, so that doesn’t help me.)
Specifically, Tracehydra means using Treehydra to translate the Spidermonkey (SM hereafter) C code that interprets each bytecode into C that emits equivalent (to the C) Tamarin IL. So I guess it reduces the problem from translating SM bytecode TT IL to translating SM C cases to TT IL-building code. Put that way, it’s not clear this actually helps, but I think SM bytecode is believed to have complex semantics that would be difficult to code in TT IL by hand, and maybe the C in SM has fewer constructs that are easier to translate. Seems possible, anyway.
If I’m gonna make any sense out of this I need to learn something about TT IL and how the TT VM uses it.
Digging in to Tamarin. There doesn’t seem to be a lot of documentation on TT, so I thought I’d write up whatever I managed to figure out, for my own benefit at least. By the way, I’ve probably gotten some things wrong, so any TT experts are highly encouraged to correct me.
I should mention that Chris Double’s Tamarin posts have been invaluable-they are the best source I know of that explains how to actually build and run TT. And Graydon Hoare’s diagrams and comments are what got me started on having any idea where to look for anything in the code.
My first question was, what is the “life cycle” of a program run by TT? The TT shell as it exists today runs ActionScript programs, specifically ABC files (ActionScript bytecode). Once the tracer kicks in, TT is running machine code traces (e.g. x86-64 ISA). (Ugh. This is turning in alphabet soup.) What goes on in between? Here’s what I found.
By the way, this picture gives an overview. (Picture does not exist yet.)
Program Form 0: ActionScript. I followed a sample program, the simplest program I could think of that will get traced (you need a hot loop), through TT. Here’s my program:
var sum = 0;
for (var i = 0; i < 1000000; i) {
sum = i;
}
print(sum);
By the way, on my MacBook, this runs in 1.7s in interpreted mode (tracing disabled) and .28s with tracing enabled, a 6x speedup. And that includes VM startup time. For comparison, Java runs the equivalent program in .13s. (But Java gets the answer “wrong”, because ActionScript uses unlimited-precision integers while Java uses int32s. So this test is unfavorable toward TT.) Excluding startup time, Java takes about 4ms, apparently, the same as C. I’ll have to retest TT excluding startup time, once I figure out how.
Program Form 1: ABC. This is the ActionScript bytecode and is the input to the current Tamarin shell. I don’t need to know too much about this, but the real Tamarin stuff is generated from here, so I peeked at the ABC for my program. ABC is apparently a stack-based bytecode language, much like Java bytecode. Here’s a snippet from my sample program, with my annotations after //:
// var sum = 0;
// sum was assigned local variable ’slot 0′ in ABC file headers
// Stack starts as: [stuff]
pushbyte 0
// Pushed a 0 value onto the stack. Stack is now: [stuff] 0
getglobalscope
// Pushed the global ‘this’ onto the stack. Stack is now: [stuff] 0 this
swap
// Swapped top 2 elements of stack. Stack is now: [stuff] this 0
setslot 1
// Stored top of stack into slot 1 of next stack element. Stack is now: [stuff]
I’m not entirely sure how the compiler writers manage to get all swap, over, dup, pick3, etc. operators right, but the code itself is understandable enough.
Transformation 0->1: ActionScript->ABC. This can be done externally to TT by the ActionScript Compiler, ASC, which is part of the Flex SDK.
Program Form 2: IL. Tamarin IL is yet another stack-based bytecode. This is the IL that the VM executes directly when in interpreter mode. The basic operations include:
Stack manipulators, such as DUP, DROP, OVER,
Arithmetic and logical operators, such as IADD,
Control flow operators, such as LBRT,
Object and variable storage operators, such as SETSLOTVALUE_I,
Interpreter internals operators, such as _debugenter, verify_x, and
Weird stuff like op_ROTNAME2_SWAP_ROT_SETRT.
I think the weird stuff might be “superinstructions”, which are instructions that just implement a short sequence of basic instructions. Apparently they help interpreters run faster because by reducing decode overhead, like old CISC processors.
These instructions are defined in files named core/vm_*.h, e.g., vm_min_interp.h. These files are heavily macroized, which allows the actual meaning to be controlled by defining those macros in different ways, although I’m not sure exactly how this feature is used yet. Here’s IADD:
INTERP_FOPCODE_INTERP_BEGIN(IADD)
/* IADD None {’stktop’: 0} */
const int32_t tmp_i_0 = int32_t(sp[-1].i) int32_t(sp[0].i) ;
INTERP_ADJUSTSP(-1)
sp[0].i = tmp_i_0;
INTERP_INVALBOXTYPE(sp[0])
INTERP_FOPCODE_INTERP_END(IADD)
As you can see, it adds the top two elements of the stack (sp) as integers, cuts the top element off the stack, and stores the sum in the new stack top. There’s also some junk about invalidating the box type, which seems to be some kind of debugging feature. When this is included in VMInterp.cpp, the begin and end macros will turn it into a switch case. From VMInterp.ii in my build:
foplabel_IADD: { pre_interp(interp, f, ip -1, sp, rp);
const int32_t tmp_i_0 = int32_t(sp[-1].i) int32_t(sp[0].i) ;
sp = (-1);
sp[0].i = tmp_i_0;
do { } while (0);
goto *k_foplabels_interp[*ip ]; }
pre_interp just prints out a trace of the instruction if the interpreter is in verbose mode and a bunch of other conditions are true. The “computed goto” at the end is an indirect jump to the case for the next instruction. This is some kind of optimization but I’ve never gotten a really convincing answer as to why it works, or if in fact it works, so I won’t go into it here. Processor experts, feel free to educate me.
The main control flow operators (i.e., used for if) seem to be LBRT and LBRF (local branch if true/false?). LBRT branches to a selected point in the IL sequence if the top of the stack is true, interpreted as a boolean. The target is specified as an offset from the address of the LBRT instruction. The target is given in the IL stream in the 2 16-bit units immediately following the LBRT code.
I also wanted to know what a function call looks like in IL, and it was surprisingly hard to figure out for some reason that I still don’t understand. But it looks like a standard call to a JS function is through an opcode w_callprop_only or w_callprop_argcok. These opcodes don’t seem to be defined in the usual vm_*_interp.h, but somehow they are made to branch to foplabel_TRACE_super_or_extern in VMInterp.ii. That code does the usual saving of a return pointer and setting the instruction pointer. Returning is accomplished with a less mysterious w_returnvalue or w_returnvoid opcode.
The type of the instructions is FOpcode, which is a 16-bit int.
Transformation 1->2: ABC->IL. This is where Tamarin starts. This step is really important because some other system, like Tracehydra, that wants to use Tamarin, should basically do the same thing, except for some other form of input instead of ABC.
Tamarin performs this transformation on one method at a time, which is typical of JITs. The transformation is perfomed by Verifier::verify, which simultaneously verifies the ABC (checks for ill-formed ABC, like the Java bytecode verifier) and outputs Tamarin IL. The entry point to the verifier is apparently Interpreter::verify_x, which is just the implementation of an IL instruction also called verify_x.
That last part was probably pretty confusing. It surprised me, at least. It means the interpreter is already running IL by the time it actually translates and runs any ABC. I think what this means is that when the shell starts up, it starts the interpreter with a bit of boilerplate IL. The IL itself has code to verify and run the ABC program.
[Warning: compiler-expert-level material.] The verifier works as an abstract interpretation of the ABC. It uses the information gathered both to check for problems with the ABC and to guide IL generation. The state of the abstract interpretation is an abstraction of the ABC stack, just a list of types of objects on the stack, along with a lot of flags describing other conditions.
A standard abstract interpreter works as a fixed-point solver that possibly makes several iterations over the code. But TT’s verifier doesn’t work like that at all. The reason is that it requires that the states be equal at every join point, otherwise the ABC is invalid. So if the ABC is valid, then the interpreter never needs to look at a given instruction twice. And because backward branches in the ABC exist only for loops, this means the verifier can just run in a single forward pass through the ABC bytecode sequence. But it’s still really an abstract interpreter. Pretty neat. [End super-hard stuff.]
So the verifier runs over the ABC in sequence, always tracking the current abstract stack state. For each instruction, it generates IL. Part of generating the IL is generating any IL needed to fetch operands-the verifier can use the stack state to figure out where they are. After generating IL, the verifier simulates the effect of the instruction on the stack. This is all handled by a big switch on the ABC opcode, and each case has separate logic to generate IL and simulate the results.
The actual writing of the bits and bytes of IL is delegated to a class MethodWriter, which in turn delegates to ForthWriter (there’s that Forth stuff again). ForthWriter is a small class that maintains a buffer of IL bytecodes. It has a small API with methods like emit_simple(), which emits a simple IL instruction. MethodWriter is a wrapper used to generate Forth from ABC. The MethodWriter API takes ABC instructions as input and then tells the ForthWriter to emit the corresponding Forth bytecodes. For ABC opcodes with a direct IL equivalent, it looks up the equivalent in k_abc_opcode_map, which ultimately comes from vm_*_codepool.h. Otherwise it just has to work a little harder.
Time for a little example. I’ll use the same snippet I used above, with the IL translation trace straight out of the log file:
frame: global * * global
2:pushbyte 0
000D LITC0
000E w_ibox
frame: global * * global int
4:getglobalscope
000F OVER
frame: global * * global int global
5:swap
0010 SWAP
frame: global * * global global int
6:setslot 1
0011 LITC4
0012 w_ck_setslot_box
frame: global * * global
I had no idea what any of this was the first time I looked at it. There are 3 kinds of lines. First, the “frame: ” lines are the abstract interpreter’s stack state (”stack frame”) at each point. Second, the lines that start with numbers are ABC bytecodes. Third, the lines that start with “ ” are the IL translation of the ABC code just above them.
The first bytecode:
frame: global * * global
2:pushbyte 0
000D LITC0
000E w_ibox
frame: global * * global int
‘pushbyte 0′ in ABC pushes the value 0 onto the stack. In IL, this is two steps: first, an opcode that pushes the literal C int value 0 (i.e., a machine word of 0 bits), then an opcode that boxes that C int into a Box. Box is Tamarin’s standard value type that can hold anything. To C, a Box looks like an IEEE-754 64-bit NaN. I guess any float that has an exponent (bits 52-62) of all 1s and a fraction that is not all 0s is a NaN, so there are really 2^53-1 different NaN values. Tamarin cleverly uses only one of those in floating-pointer computations so it can pack other data types, like 32-bit ints, into the 2^53-2 spare NaNs. A Box starting with the bit pattern 1111111111000 is an int, and the rightmost 32 bits contain the int data. See Box.h.
In our example, note how the verifier knows the top of the stack now holds an int.
The second bytecode:
frame: global * * global int
4:getglobalscope
000F OVER
frame: global * * global int global
This is kind of interesting. An object-model-type ABC instruction, getglobalscope (pushes scope to use for unqualified name lookups), got translated into a stack manipulation IL instruction, OVER (pushes the value just under top of the stack). Apparently, the global ‘this’ scope goes on the stack at the start of a method, and the interpreter records its position. If no other scopes have been entered (no with blocks), then the verifier can just emit an instruction to pick it from its current depth in the stack, since of course the interpreter also always knows the stack size. If there are other scopes in play, then the verifier emits a w_getouterscope instruction, which calls the interpreter C method Interpreter::getscopeobj, which goes through a few levels of direction but is ultimately pretty simple, grabbing a scope chain for the current method, and then picking off the first scope. Well, I really don’t know what that means, because I’m not too clear on scope chains yet, but it’s only a few lines of code, anyway.
That’s enough for now. [Less]
Posted
about 17 hours
ago
by
beltzner
Please note: The Firefox 3 Release Candidate is a public preview release intended for developer testing and community feedback. It includes new features as well as dramatic improvements to performance, memory usage and speed. We recommend that you
... [More]
read the release notes and known issues before installing this release.
The first Firefox 3 Release Candidate is now available for download. This milestone is focused on testing the core functionality provided by many new features and changes to the platform scheduled for Firefox 3. Ongoing planning for Firefox 3 can be followed at the Firefox 3 Planning Center, as well as in mozilla.dev.planning and on irc.mozilla.org in #granparadiso.
New features and changes in this milestone:
Improvements to the user interface based on user feedback, including changes to the look and feel on Windows Vista, Windows XP, Mac OS X and Linux.
Changes and fixes for new features such as the location bar autocomplete, bookmark backup and restore, full page zoom, and others, based on feedback from our community.
Fixes and improvements to platform features to improve security, web compatibility and stability.
Continued performance improvements: changes to our JavaScript engine as well as profile guided optimization continues to improve performance over previous releases as measured by the popular SunSpider test from Apple, and in the speed of web applications like Google Mail and Zoho Office.
(You can find out more about all of these features in the “What’s New” section of the release notes.)
Testers can download the Firefox 3 Release Candidate builds for Windows, Mac OS X and Linux in over 45 different languages. Developers should also read the Firefox 3 for Developers article on the Mozilla Developer Center.
Note: Please do not link directly to the download site. Instead we strongly encourage you to link to this Firefox 3 Release Candidate announcement so that everyone will know what this milestone is, what they should expect, and who should be downloading to participate in testing at this stage of development. [Less]
Posted
about 19 hours
ago
by
david.humphrey
I’m too tired to write this properly, but it’s satisfying enough to do before I quit. If you’ve been following my progress, you’ll know that I’ve been trying to solve Dave’s mxr-dehydra challenge, looking for all possible methods that
... [More]
SetParent could be in privatePrevAccessible->SetParent(this) (which is really nsPIAccessible->SetParent(nsIAccessible*)). As Dave discovered the hard way, there are two. Using my code, which builds a SQLite database of the tree’s type info while you build, I can do it in a fraction of a second:
sqlite> select members.mtname, members.mdecl, members.mdef from impl, members where impl.tbase="nsPIAccessible" and impl.tconcrete=members.mtname and mname="SetParent(nsIAccessible*)";
mtname|mdecl|mdef
nsAccessible|/home/dave/mozilla-central/src/accessible/src/base/nsAccessible.h:111|/home/dave/mozilla-central/src/accessible/src/base/nsAccessible.cpp:460
nsHTMLListBulletAccessible|/home/dave/mozilla-central/src/accessible/src/html/nsHTMLTextAccessible.h:110|/home/dave/mozilla-central/src/accessible/src/html/nsHTMLTextAccessible.cpp:338
This shows the declaration and definition of nsAccessible::SetParent and nsHTMLListBulletAccessbile::SetParent. I’ve written a dehydra script to generate .sql files for everything that gets compiled, and then a script to assemble these into a simple database (~45M) that can be queried about any class/type, member, or inheritance relationship in the tree.
I’ve run into all sorts of strange edge cases over the past two days, but it’s getting pretty close. The cases I’ve tested work, which isn’t the same as saying it works. I’m going to try and iron out some more of the bugs I know about, and then move on to solving the problem of how to map tokenized source to the output of process_function(), which breaks down all the variables, assignments, function calls within the code. The thought of it overwhelms me tonight, and it’s enough to make me want to quit for the weekend. But I’m quitting with a smile on my face :). [Less]
java development chrome gecko xhtml css browser www firefox client html web internet mozilla javascript http xul gtk windows
|
edit tags
