Septembre 2010 - Tachyon-list - mailman.iro.umontreal.ca

Code generation draft
by Marc Feeley 04 Oct '10

04 Oct '10

Here are my notes for x86 code generation for some of the IR primitives. Note that the code generation logic contains optimizations (for example testing equality with 0, moving a register to itself, etc) and also some required tests (in sub_ovf the case where the destination register is the same as the second operand, to avoid clobbering the second operand). Marc ------------------------------------------------------------------------------- rptr $t_1 = get_ctx; no-op. register allocator should assign context register to $t_1 ------------------------------------------------------------------------------- box $t_1 = load_box $t_2, K; movq K( %REG($t_2) ), %REG($t_1) ------------------------------------------------------------------------------- i64 $t_1 = and_box_i64 $t_2, K; if K = 0 then xorq %REG($t_1), %REG($t_1) else if %REG($t_1) != %REG($t_2) then movq %REG($t_2), %REG($t_1) endif andq $K, %REG($t_1) endif ------------------------------------------------------------------------------- i64 $t_1 = and_box_i64 $t_2, $t_3; if %REG($t_2) = %REG($t_3) then if %REG($t_1) != %REG($t_2) then movq %REG($t_2), %REG($t_1) endif elsif %REG($t_1) = %REG($t_2) then andq %REG($t_3), %REG($t_1) elseif %REG($t_1) = %REG($t_3) then andq %REG($t_2), %REG($t_1) else movq %REG($t_2), %REG($t_1) andq %REG($t_3), %REG($t_1) endif ------------------------------------------------------------------------------- i8 $t_1 = eq_i64 $t_2, K; if K = 0 then testq %REG($t_2), %REG($t_2) else cmpq $K, %REG($t_2) endif movb $0, %REG($t_1) cmoveb $1, %REG($t_1) ------------------------------------------------------------------------------- i8 $t_1 = eq_i64 $t_2, $t_3; cmpq %REG($t_2), %REG($t_3) movb $0, %REG($t_1) cmoveb $1, %REG($t_1) ------------------------------------------------------------------------------- if_i8 $t_1 then lbl1 else lbl2; testb %REG($t_1), %REG($t_1) if the if_i8 instruction is immediately followed by lbl1 then je lbl2 elsif the if_i8 instruction is immediately followed by lbl2 then jne lbl1 else jne lbl1 jmp lbl2 endif ------------------------------------------------------------------------------- box $t_1 = add_ovf $t_2, K normal lbl1 overflow lbl2; if %REG($t_1) != %REG($t_2) then movq %REG($t_2), %REG($t_1) endif if K = 1 then incq %REG($t_1) else addq $K, %REG($t_1) endif if the add_ovf instruction is immediately followed by lbl1 then jo lbl2 elsif the add_ovf instruction is immediately followed by lbl2 then jno lbl1 else jno lbl1 jmp lbl2 endif ------------------------------------------------------------------------------- box $t_1 = add_ovf $t_2, $t_3 normal lbl1 overflow lbl2; if %REG($t_1) != %REG($t_2) then movq %REG($t_2), %REG($t_1) endif addq %REG($t_3), %REG($t_1) if the add_ovf instruction is immediately followed by lbl1 then jo lbl2 elsif the add_ovf instruction is immediately followed by lbl2 then jno lbl1 else jno lbl1 jmp lbl2 endif ------------------------------------------------------------------------------- box $t_1 = sub_ovf $t_2, K normal lbl1 overflow lbl2; if %REG($t_1) != %REG($t_2) then movq %REG($t_2), %REG($t_1) endif if K = 1 then decq %REG($t_1) else subq $K, %REG($t_1) endif if the sub_ovf instruction is immediately followed by lbl1 then jo lbl2 elsif the sub_ovf instruction is immediately followed by lbl2 then jno lbl1 else jno lbl1 jmp lbl2 endif ------------------------------------------------------------------------------- box $t_1 = sub_ovf $t_2, $t_3 normal lbl1 overflow lbl2; if %REG($t_2) = %REG($t_3) then xorq %REG($t_1), %REG($t_1) else if %REG($t_1) = %REG($t_3) then movq %REG($t_3), %TEMP movq %REG($t_2), %REG($t_1) subq %TEMP, %REG($t_1) // note: %TEMP can be a free register, stack or context slot else if %REG($t_1) != %REG($t_2) then movq %REG($t_2), %REG($t_1) endif subq %REG($t_3), %REG($t_1) endif if the sub_ovf instruction is immediately followed by lbl1 then jo lbl2 elsif the sub_ovf instruction is immediately followed by lbl2 then jno lbl1 else jno lbl1 jmp lbl2 endif endif -------------------------------------------------------------------------------

5 12

Another interesting benchmark: Visual Transistor-level Simulation of the 6502 - in Javascript
by Erick Lavoie 20 Sep '10

20 Sep '10

Visual Transistor-level Simulation of the 6502 - in Javascript. http://jwz.livejournal.com/1292645.html

2 1

Fwd: [CfP] 4th European Lisp Symposium, Hamburg, March 31st - April 1st 2011
by Marc Feeley 16 Sep '10

16 Sep '10

This might be a good place to publish some first results. It is the "Lisp" symposium, but they accept papers on any language in the Lisp family including ECMAScript. Marc Begin forwarded message: > From: Didier Verna <didier(a)lrde.epita.fr> > Date: September 13, 2010 7:58:49 AM EDT > To: Didier Verna <didier(a)lrde.epita.fr> > Subject: [CfP] 4th European Lisp Symposium, Hamburg, March 31st - April 1st 2011 > > > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > 4th European Lisp Symposium > Special Focus on Parallelism & Efficiency > > March 31 - April 1st, 2011 > TUHH, Hamburg University of Technology > Hamburg, Germany > > http://www.european-lisp-symposium.org/ > > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > > > Important Dates > ~~~~~~~~~~~~~~~~ > + Submission Deadline: January 09, 2011 > + Author Notification: February 06, 2011 > + Final Paper Due: February 28, 2011 > + Symposium: March 31 - April 1st, 2011 > > Authors of accepted research contributions will be invited to submit > an extended version of their papers for journal publication. > > > Scope > ~~~~~~ > The purpose of the European Lisp Symposium is to provide a forum for > the discussion and dissemination of all aspects of design, > implementation and application of any of the Lisp dialects, including > Common Lisp, Scheme, Emacs Lisp, AutoLisp, ISLISP, Dylan, Clojure, > ACL2, ECMAScript, Racket and so on. We encourage everyone interested > in Lisp to participate. > > The European Lisp Symposium 2011 invites high quality papers about > novel research results, insights and lessons learned from practical > applications, and educational perspectives. We also encourage > submissions about known ideas as long as they are presented in a new > setting and/or in a highly elegant way. > > This year's focus will be directed towards "Parallelism & Efficiency". > We especially invite submissions in the following areas: > > + Parallel and distributed computing > + Code generation for multi-core architectures > + Code generation for HTM > + Large and ultra-large systems > + Optimization techniques > + Embedded applications > > Contributions are also welcome in other areas, including but not > limited to: > > + Context-, aspect-, domain-oriented and generative programming > + Macro-, reflective-, meta- and/or rule-based development approaches > + Language design and implementation > + Language integration, inter-operation and deployment > + Development methodologies, support and environments > + Educational approaches and perspectives > + Experience reports and case studies > > > Technical Program: > ~~~~~~~~~~~~~~~~~~ > We invite submissions in the following forms: > > * Papers: Technical papers of up to 15 pages that describe original > results or explain known ideas in new and elegant ways. > > * Demonstrations: Abstracts of up to 4 pages for demonstrations of > tools, libraries, and applications. > > * Tutorials: Abstracts of up to 4 pages for in-depth presentations > about topics of special interest for at least 90 minutes and up to > 180 minutes. > > * Lightning talks: Abstracts of up to one page for talks to last for > no more than 5 minutes. > > All submissions should be formatted following the ACM SIGS guidelines > and include ACM classification categories and terms. For more > information on the submission guidelines and the ACM keywords, see: > http://www.acm.org/sigs/publications/proceedings-templates > http://www.acm.org/about/class/1998 > > Submissions should be uploaded to Easy Chair, at the following address: > http://www.easychair.org/conferences/?conf=els2011 > > > Programme Chair > ~~~~~~~~~~~~~~~~ > Didier Verna - EPITA Research and Development Laboratory, France > > Local Chair > ~~~~~~~~~~~~ > Ralf Moeller - Hamburg University of Technology, Germany > > Programme Committee > ~~~~~~~~~~~~~~~~~~~~ > Antonio Leitao - Instituto Superior Tecnico/INESC-ID, Portugal > Christophe Rhodes - Goldsmiths College, University of London, UK > David Edgar Liebke - Relevance Inc., USA > Didier Verna - EPITA Research and Development Laboratory, France > Henry Lieberman - MIT Media Laboratory, USA > Jay McCarthy - Brigham Young University, USA > Jose Luis Ruiz Reina - Universidad de Sevilla, Spain > Marco Antoniotti - Universita Milano Bicocca, Italy > Manuel Serrano - INRIA, France > Michael Sperber - DeinProgramm, Germany > Pascal Costanza - Vrije Universiteit of Brussel, Belgium > Scott McKay - ITA Software, USA > > > -- > Resistance is futile. You will be jazzimilated. > > Scientific site: http://www.lrde.epita.fr/~didier > Music (Jazz) site: http://www.didierverna.com

2 1

Tag Bits, Feedback Wanted
by Maxime Chevalier-Boisvert 12 Sep '10

12 Sep '10

We're getting to the point where we need to pick tag bits for boxed values in order to implement our system. I've looked at our previous notes and wrote down the following tentative scheme: Tags needed: - immediate int X----X000 0 - object X----X111 7 - function obj X----X110 6 - array obj X----X101 5 - float X----X100 4 - string X----X011 3 - constants X----X010 2 - bool/null/undef - other X----X001 1 - (getter-setter, hash table, etc.) All tags are 3 bits wide, which has the advantage of making it easy to extract the tag, always using the same mask operation (val & MASK). I have picked the tags 7, 6 and 5 for objects, functions and arrays, because those 3 can all have properties stored on them, and so might share a similar memory layout (eg; might have a prototype pointer, a hash table pointer, etc, at the same offset, they are all objects). This makes it possible to test if something is "an object" by doing (val & MASK >= 5). This scheme has 8 possible tags. The last one, "other", is for all the things that may exist in our heap but won't necessarily have a reserved tag. These include getter-setter objects, hash tables, and other possible runtime objects that may end up in the garbage-collected part of the heap. Some question worth considering are: 1) Could we do away with some of these tags? 2) Are there other things worth tagging that are not included in there? Do we need more tags? 3) Would it be worthwhile to pick a different/more complex encoding scheme, so as to gain 1 or 2 extra bits for immediate integers, or have a simpler (one-bit?) check for "is an object"? - Maxime

3 2

Re: [Tachyon-list] Execution model and register usage on x86 and
by Erick Lavoie 08 Sep '10

08 Sep '10

I put the original mail in a document on google docs. I didn't bother answering individually to each mail so here are my answers. Handlers and runtime context (RC): _Size_ At first I wanted to avoid duplication between the different RCs but let's see how much memory would really be used if things got duplicated. Let's assume for now that the RC might contain the global object reference, the root object reference, the heap pointer and all the handlers. Maxime talked of ~100 handlers so I'll take her word for it. So the size of the RC object would be ~400 or ~800 bytes depending on the platform (the 3 references becomes negligible). Given something like 100 instances of tachyon (1 per browser tab for a super power user) the memory used for that would be ~40 or ~80 kB. I don't know how many "objects from the low-level Javascript library" Maxime was referring to but as long as it is 10-100 references, it still seems reasonable. However, we should not plan on supporting something like 100 000 user-level threads, each with their own RC, using this scheme. _Switching_ If I understand the problem correctly, different user-level instances of tachyon should never be able to directly call functions or access objects from one another. So the two cases that might require a context change are between the VM and a user-level instance (such as saving/resuming the execution of an instance) or between a user-level instance and the VM (such as calling the compiler with eval). In the first case, the VM should have access to all instance contexts to manage them so I guess the context changes will be manually coded where we need them. In the second case, I see two ways of handling the problem. My first idea is that we might identify which calls might result in a context switch (like eval) and add the necessary code on the caller side. My second idea is that we might use an "expected context" on the callee side. Each compiled function would have an expected context that would be associated with it at linking time. An expected context is the reference to a runtime context object. The expected context would be checked at the function entry. Three cases might happen: 1. The current context is the same as the expected context. Nothing would be done. 2. The current context is different from the expected context. The current context is saved on the stack, and replaced by the expected context. The current context would be restored when returning from the function. 3. The expected context is a special "identity value" which would make the function behave as in (1), whatever context is currently active. This would allow standard library functions to work with both the compiler and the user-level code without having to duplicate them (as in a statically linked context). The runtime overhead would be 1 check at each function entry and 1 check at each return point. The space overhead would be 1 reference in each stack frame where there is a context change. Once the context has been changed, subsequent calls to functions expecting the same context would not incur an additional space overhead. _Interesting Configurations_ I initially decided to separate the different conceptual elements in case some other interesting combinations could be found along the way. However, it doesn't mean that all combinations are interesting. As Marc pointed out, having only handlers accessible from registers might not be worth it. So here is a listing of which combinations I think might be worth trying. I call a unique combination, a scenario. As a reminder the different elements are: -Stack Pointer (SP) -Heap Pointer (HP) -Runtime Context (RC) -Handlers (Hdlr) -Argument Nb (ArgNb) -Return Address (RA) -Implicit Args (ImpArg) -Explicit Args (ExpArg) REG is any of X86_REG or X64_REG. Non-specified items are passed on the stack or accessible from memory as globals. ExpArg(k) means first k args of ExpArg. Worst-Case 1. Only the stack pointer (SP) in a register. Everything else passed on the stack or accessible globally. Used as a base reference to calculate the speedup achieved by passing things in registers. Maximize of function arguments passing 2. SP in xSP, ImpArg and ExpArg(5) in registers; Predominance to runtime context accesses 3. SP in xSP, RC in REG, HP, Hdlr, ArgNb accessible from RC, ImpArg and ExpArg(4) in registers; Predominance to object allocation 4. SP in xBP, HP in xSP, ImpArg and ExpArg(4) in registers; RC + Object allocation 5. SP in xBP, HP in xSP, RC in Reg, HP, Hdlr, ArgNb accessible from RC, ImpArg and ExpArg(3) in registers; RC + Return Address 6. SP in xSP, RA in Reg, RC in Reg, HP, Hdlr, ArgNb accessible from RC, ImpArg and ExpArg(3) in registers; Most of runtime elements 7. SP in xBP, HP in xSP, RA in Reg, RC in Reg, HP, Hdlr, ArgNb accessible from RC, ImpArg and ExpArg(2) in registers; In each scenario, the total number of registers reserved for register allocation is always ImpArg + ExpArg(k). Further things to try would be: - Passing the ImpArg on the stack; - Making RA and maybe some other registers callee-save to liberate them for register allocation, possibly selectively for functions with certain properties (like more than n temporaries). I would suggest doing this once we figured which scenario works best. I am not settled yet on how the code generation will be parametrized since non-trivial changes to handlers might be required for the different configurations to work. I'll see when we agree on a number of interesting scenarios. Erick

2 1

Fwd: 9th Compiler-Driven Performance Workshop - CASCON 2010
by Marc Feeley 07 Sep '10

07 Sep '10

This would be a good workshop to present the Tachyon project. Let's talk about it at the next meeting (August 16). Marc Begin forwarded message: > From: clark verbrugge <clump(a)cs.mcgill.ca> > Date: August 6, 2010 3:06:48 PM PDT > To: undisclosed-recipients:; > Subject: 9th Compiler-Driven Performance Workshop - CASCON 2010 > > 9th Compiler-Driven Performance Workshop > November 4, 2010 (Thursday) > > Hilton Suites Toronto/Markham Conference Centre > Associated with CASCON 2010 > (http://www.cas.ibm.com/cascon) > (Nov 1-4 2010) > > Dear Colleague: > > We would like to invite you to participate in the 9th Compiler-Driven > Performance Workshop (CDP10) which will be held during the IBM Center for > Advanced Studies Conference (CASCON) 2010 in Markham, Ontario, Canada. > > In the past seven years we had very successful one-day events in which faculty > members, students and practitioners presented their recent work and research > plans. > > Topics to be discussed in the workshop include, but are not limited to: > > * innovative analysis, transformation, and optimization techniques > > * languages, compilers, and optimization techniques for multicore processors > and other parallel architectures > > * compiling for streaming or heterogeneous hardware > > * dynamic compilation for high-performance and real-time environments > > * compilation and optimization for scripting languages > > * compilation techniques for reducing power > > * tools and infrastructure for compiler research > > > SUBMISSION: > > NO LATER THAN WEDNESDAY AUGUST 24, we would like to hear from you if you > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ > would like to give a talk about your research or to volunteer a student to do > so. Please send, by email to clump(a)cs.mcgill.ca, your talk title, the > author list, the name of the speaker, and a brief abstract. > > Please note that the number of presentation slots is quite limited. Once we > have a list of title/speakers, we will let you know if your presentation has > been selected. > > CDP does not publish proceedings. Presenters are required to provide an > electronic copy of their slides. The slides will be available on a website soon > after the workshop. > > CASCON has a very well organized exhibit section that is an excellent forum to > display students' current work and allow for discussions. We would like to > suggest that you encourage some of your students to participate in the exhibit > section. > > We also would like to encourage all participants to gather during the lunch and > coffee breaks for more informal interactions. The workshop does not have funds > to defray the travel/lodging costs for participants/speakers. However > registration for CASCON is free, and lunch is provided to all attendees. > > We look forward to your participation in CDP10! > > Steering Committee: > Kit Barton - IBM Toronto Lab > David Grove - IBM Watson > Ondrej Lhotak - University of Waterloo > J. Gregory Steffan - University of Toronto > Mark Stoodley - IBM Toronto Lab > Clark Verbrugge - McGill University > > -- > ttfn, > clark > clump(a)cs.mcgill.ca >

5 34

HashMap
by Marc Feeley 07 Sep '10

07 Sep '10

Maxime, I started working on the parser and notice that you use a "HashMap" in parser/ast-passes.js . This type of object is not defined in the ECMAScript specification. Can you modify your code to not use non-standard features, or provide a portable implementation of HashMaps. Marc

2 1

Execution model and register usage on x86 and x86-64
by Erick Lavoie 07 Sep '10

07 Sep '10

I am trying to first clarify what elements are necessary for program execution and which of those might be worth putting in registers. I call register usage configuration which of those elements are put in a register and which are located in memory. I am trying to anticipate the different configurations we might want to try to see what is worth being made configurable. Feel free to add anything you think should be included and any ideas of optimizations that might have an impact on register usage. __Definitions__ X86_REG means any of EAX, EBX, ECX, EDX, ESI, EDI, EBP, ESP X64_REG means any of RAX, RBX, RCX, RDX, RSI, RDI, RBP, RSP, R8-R15 REG means any one of X86_REG or X64_REG (depending on the platform) excluding those previously used for a special purpose MEM means an emplacement in memory either accessible from the context or the stack. GLO means an emplacement in memory determined at linking time (like a global variable) which can be seen as static from the runtime code. Here are the elements we might want to put in a register or not. Possible configurations are given between brackets separated by commas. __Runtime elements and possible configurations__ Stack Pointer (xSP, xBP): Mark suggested using xBP to possibly use xSP for object allocation and I am also including xSP in case we might want to keep it in the standard location ( Would it simplify a future Foreign Function Interface?). Heap Pointer (xSP, GLO): Pointer to the remaining free space on the heap when using a compacting GC, like stop&copy or to the beginning of the free list when using a non-compacting GC like mark&sweep. If not in a register, I would suggest having it as a global variable since it is common to all Runtime Contexts. Runtime Context (REG, GLO): Contains all the information specific to a given instance of tachyon. An instance might be a browser tab/window or the compiler itself. The runtime context is an object in memory containing minimally the global object and the root object (Object.prototype). The runtime context object might contain handlers references when accessed from a register to preserve a register for other usage. Handlers (REG, GLO): Contains references to general handlers to perform the general but less common case for various operations such as additions, multiplication, etc. or for expensive but less common operations such as exception handling. When accessed from a register, the handlers references might be put at the end of the runtime context object. Argument Nb (REG, MEM): The number of arguments given by the caller of a function. When in a register, can be combined with the Runtime Context to save a register, given that the context object are aligned to a given value, liberating the lower bits of the Runtime Context register. When in memory, it will be saved on the stack as part of the function call protocol. Return Address (REG, MEM): Return address of the currently executing function. Whether in memory or in a register, it will be saved, restored or set as part of the function call protocol. Implicit Function Arguments (2 REG, REG + MEM, MEM): Arguments to a function not explicitly part of the function definition (not given between the brackets), such as the function reference (when arguments.callee is used or when calling a closure) and the this object, which can either be any object or the global object. When passed in registers, each implicit argument use a different register. When passed in memory, they are passed on the stack. In the two cases, this is part of the function call protocol. I separated them from the explicit function arguments because it might happen that most functions in a real world application are not used in an object-oriented style or as closures so it would liberate two registers for other arguments. If the distinction turns out not to be really useful, we might simply consider all of the arguments as explicit function arguments in the same order as given in the current IR. Explicit Function Arguments (k REG + (n-k) MEM): Arguments to a function explicitly part of the function definition (given between the brackets). k are the first k arguments given to a function call from left to right and n is the total number of arguments given to that function call. k is a register usage configuration parameter that applies to the whole program. n is the specific number of arguments at a given call site. The first k arguments are passed in registers and the remaining (n-k) arguments are passed on the stack. The parameter k is part of the function call protocol. That's it! As a complementary discussion, so far I have assumed that every register was caller-save. Do you guys think that it might be worth reserving some registers to be callee-save? In that case, when those should be spilled, at the entry of a function or at the site of usage? Erick

3 5

SPLASH 2010: early registration ending on september 16th
by Erick Lavoie 07 Sep '10

07 Sep '10

We have 10 days left for early registration. Since I don't want to miss a week of classes, I won't go this year, so I guess it will be the two of you, Marc and Maxime! Erick

3 3

Required Parser Fixes
by chevalma＠iro.umontreal.ca 03 Sep '10

03 Sep '10

Marc, do you have any time to fix the parser issues we discussed before leaving? There are a few things I'd like to fix in the IR conversion that I'd can't really do until those fixes are applied. Things to fix: - Identifier/variable objects not the same (not ===) for function parameters vs locals that are parameters - Scope of var declarations inside catch not matching JS semantics - Function declarations inside catch resolve their variable to the outer containing function, not the catch scope (but function expressions behave as you would expect) - arguments variable should not appear free, should be a local Feature requests: - function/program prologue annotations extraction, functions should have a field that is a list of all prologue annotation strings - when eval appears free in a function or a sub-function, make all variables "escaping" all the way to the function containing the eval, to signal that they could all be captured by a closure corresponding to eval code - Maxime

3 2