Tachyon-list Juillet 2010

tachyon-list@iro.umontreal.ca

4 participants
8 discussions

Code generation: Fibonacci and listing working
by Erick Lavoie 26 Jul '10

26 Jul '10

A hand-coded version of Fibonacci is shown in "test-x86-fibonacci.js". To run a test of fib(40) and show the corresponding listing of the assembly code, run: ./fib.sh in the codegen directory, assuming the extension made by Marc to d8 has been applied. I've merged all my changes in the master branch and those are available on the repository. I'll test everything thoroughly for the rest of the day, I've found that it is pretty easy to introduce typo bugs in Javascript ;-). Erick

6 17

Current SSA form of a call instruction prevents usage of fixed intervals
by Erick Lavoie 25 Jul '10

25 Jul '10

In trying to add Fixed interval support on the register allocation algorithm, to preserve registers across call sites, I ran into a problem with our current representation. Given a call instruction like this: 20: ... 22: (9) $t_9 = call $t_8, global, $t_7 continue call_cont 24: ... I need to be able to express the fact that all registers will be used during a function call. The algorithm given in the paper expresses it by assigning a live range interval [22,23[ for all registers. They call this a fixed interval. This effectively forces all live values in registers to be spilled at a function call site, because their own live range intersect with the fixed interval. However, given our current notation, I would say that 't_9' starts being live at 22, which intersects with the fixed interval of any of the registers. For the fixed interval to be used correctly, I would need to be able to express the fact that the return value live range starts right after the fixed interval ends, in this case $t_9 = [23,...[. I see it as a decoupling between the function call and the return value. At this point, I don't know if this could have unintended consequences down the road and I would like your opinion on this. Erick

3 3

IR Refactoring Ideas
by Maxime Chevalier-Boisvert 22 Jul '10

22 Jul '10

I've started a refactoring of the IR instructions code. I implemented a function called GenericInstrMaker, which constructs a closure to be used as an instruction constructor. This is meant to be a quick way to create new "classes" for instructions that follow a generic pattern (eg: all arithmetic, comparison, bitwise, logical operators). Erick and I have also been discussing introducing some x86 instruction classes into the IR for code generation and register allocation purposes, which made me think it would be nice to have an "X86Instr" class in our instruction class hierarchy. However, this somewhat breaks my current model, because, some x86 instructions will be branch instructions, but these can't have both X86Instr and BranchInstr as their prototype. Hence, I've been thinking that perhaps, instead of having a BrancInstr class, all instructions should have an "isBranch" boolean flag. I was also thinking that instructions could have other flags, such as a "write" flag, and a "read" flag, to indicate that some instructions have memory access side effects. These side effect flags would be useful for writing an IR optimizer, later on. Any comments on those ideas? - Maxime

3 3

Code Generation Assembly Syntax proposal
by Erick Lavoie 12 Jul '10

12 Jul '10

I've been tinkering with Javascript and x86_64 assembly code and in doing so, I've tried to achieve a syntax in Javascript as close as possible to the AT&T syntax so that writting assembly code feels almost like inline assembly with gcc. I have not extensively surveyed all instructions yet but here is an example of what it might look like. The javascript notation and the corresponding assembly code in AT&T syntax are shown side-by-side: var a = new x86_Assembler(); a. add ($(-8), ESP). // addl $-8,%esp maintain 16 byte alignment for Mach!: push (EAX). // push %eax mov (_16(ESP), EAX). // movl 16(%esp),%eax get pointer to handlers call (_12(EAX)). // call *12(%eax) call handlers[1], printf add ($(12), ESP). // addl $12,%esp maintain 16 byte alignment add ($(-4), ESP). // addl $-4,%esp maintain 16 byte alignment push ($(11)). // push $11 dup (). // MACRO: duplicate top of stack mov (_16(ESP), EAX). // movl 16(%esp),%eax get pointer to handlers call (_16(EAX)). // call *16(%eax) call handlers[2], add add ($(12), ESP). // addl $12,%esp maintain 16 byte alignment ret (); The example above covers usage of immediate values, registers, memory accesses on 0,1 and 2 operands instructions. Notice how by having each instruction function return the "this" object, all instructions functions can be chained together. Also notice that "$", "_", "_12" and "_16" are functions which return either and immediate, or a memory access object. Finally, "ESP" and "EAX" are register objects. One interesting thing to note is the possibility to use "macros" of assembly instructions such as shown by the usage of "dup". Such macros could be installed on the "a" object for a one shot usage, therefore being limited to the scope of the "a" variable, without polluting its prototype. A definition of dup could be: a.dup = function () { return this. mov (_(ESP), EAX). // movl (%esp), %eax get top of stack value add ($(-4), ESP). // addl $-4, %esp add space on stack for the value mov (EAX, _(ESP)); // movl %eax, (%esp) copy value on top of stack } Other more useful macros could be promoted to the prototype object. To achieve that kind of syntax without polluting the global object we could use the following idiom: function () // A function or method on an object, or an anonymous function { // used as a local namespace // Definitions of used methods and objects const $ = x86_Assembler.prototype.$; const ESP = x86_Assembler.prototype.register.ESP; const EAX = x86_Assembler.prototype.register.EAX; const _ = x86_Assembler.prototype.memory._; const _12 = x86_Assembler.prototype.memory._12; const _16 = x86_Assembler.prototype.memory._16; var a = new x86_Assembler(); // Can be defined here or outside the function // Macro definitions such as "dup" // Some assembly code here }; // When used as a namespace, it should be called right away I will survey more extensively other instruction usages to see if there are corner cases. Erick

4 6

Exception handling overview
by Erick Lavoie 07 Jul '10

07 Jul '10

The following paper provides a nice overview and a clear explanation of exception handling for C++/Java, Eiffel, Smalltalk and Oberon. However, as expected, the implementation details are mostly given for their metaprogramming approach. Tachyon GDoc: http://docs.google.com/fileview?id=0BxkLUElWcqxDOTMzZGY2YmYtNjFjNy00OTVmLTk… <http://docs.google.com/fileview?id=0BxkLUElWcqxDOTMzZGY2YmYtNjFjNy00OTVmLTk…> Original link to PDF: http://ssw.jku.at/Research/Papers/Hof97b.html Erick

1 0

Function context reification proposal
by Erick Lavoie 02 Jul '10

02 Jul '10

The example given in the previous mail where a bunch of constants are declared in a function scope has brought an idea to ease declarations of such constants when there is an important number of them. It would bring module-like capabilities, decoupling the internal layout of modules from the usage made by clients of that module. If the function context could be accessed as a variable in a similar way that the global object can be accessed in the global scope through "this", we could simply write a function that installs all those declarations on the context object. Here is an example: function foo () { var context = foo.getContext(); x86.import(context); // or it could be context.import(x86) // Some cleaner code here var mem_access = _(ESP); } x86.import = function (context, /* optional */ import_list) { if(import_list) { for (var i in import_list) { context[i] = x86[i]; } } else { context["_"] = x86._; context["ESP"] = x86.register.ESP; //... } } Given that we will have access to the internals of the compiler, I think it would be a reasonable extension, after the bootstrap is done. It would however prevent us from bootstrapping on a stock javascript engine. We might find a workaround using eval but that would violate our "no-eval" policy. Erick

2 1

Bug in remItem
by Marc Feeley 01 Jul '10

01 Jul '10

There is a bug in the algorithm for deleting a key from a hash map (method remItem). Imagine the scenario where the keys are added in turn A, B, C where A and C hash to the index 1 and B hashes to the index 2. The array containing the elements will be: 0 1 2 3 4 +---+---+---+---+---+ | | A | B | C | | +---+---+---+---+---+ If the key A is removed, it will be replaced by "freeKey" and B and C will not move. But if C is then looked up in the hash map it will not be found. You really need 2 code: freeKey = this element has never contained a key (since the hash table was created or resized) deletedKey = this element used to contain a key which has since been deleted. It is possible to do away with the "deletedKey" code, but it requires (in general) rehashing the table, which is a very high price to pay. Check the Gambit sources for the algorithms in Scheme and C, or an algorithms textbook. Marc

3 8

Fwd: SIGPLAN Posting (POPL, ASPLOS, and CGO Call for Papers)
by Marc Feeley 01 Jul '10

01 Jul '10

CGO sounds like an interesting venue for our work. The deadline is in mid-september, so we might have something to say about tachyon at that point. Marc Begin forwarded message: > From: Jack Davidson <jwd(a)VIRGINIA.EDU> > Date: July 1, 2010 9:18:19 AM EDT > To: SIGPLAN-ANNOUNCE(a)LISTSERV.ACM.ORG > Subject: SIGPLAN Posting (POPL, ASPLOS, and CGO Call for Papers) > Reply-To: Jack Davidson <jwd(a)VIRGINIA.EDU> > > Dear SIGPLAN Member: > > The following message contains information about upcoming SIGPLAN > conferences and other activities that may be of interest to SIGPLAN > members. > > ******* > > * Call for Papers: 2011 SIGACT/SIGPLAN Symposium on Principles of Programming Languages (POPL 2011) > URL: http://www.cse.psu.edu/popl/11 > Location: Austin, TX > Abstract Deadline: July 8, 2010 > Full Paper Deadline: July 25, 2010 > Submitted by Mooly Sagiv <mooly.sagiv(a)gmail.com> > > * Call for Papers: 2011 Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2011) > URL: http://asplos11.cs.ucr.edu > Location: Newport Beach, CA > Abstract Deadline: July 19, 2010 > Full Paper Deadline: July 26, 2010 > Submitted by Soner Onder <soner(a)mtu.edu> > > * Call for Papers: IEEE/ACM International Symposium on Code Generation > and Optimization (CGO 2011) > URL: http://www.cgo.org > Location: Chamonix, France > Abstract Deadline: September 15, 2010 > Full Paper Deadline: September 22, 2010 > Submitted by Richard Johnson <rjohnson(a)nvidia.com>

2 1

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

Tachyon-list Juillet 2010