Exupery

exupery@lists.squeakfoundation.org

107 discussions

An update after ESUG.
by bryce＠kampjes.demon.co.uk 04 Sep '07

04 Sep '07

ESUG saw a lot of progress for Exupery. There is now a preliminary Mac port and 2 bugs were fixed. There is a Mac VM available here: http://wiki.squeak.org/squeak/3945 This version is compiled without optimisation. It looks like there's a bug in GCC 4.0.1 which is preventing sends from working in Exupery. Exupery works fine with gcc 3.3.3 and gcc 4.1.2. Hopefully there will be a more polished Mac VM soon compiled with optimisations. Thanks to Matthieu for building this. Two bugs were fixed. The major bug was due Exupery overflowing the root table, this was the one that was causing the crashes that I was debugging. There was a minor bug that was due to failing to mark Exupery's interpreter integration objects which as far as I'm aware has never caused a crash, it's fixed too. I'm starting to think about the next release seriously as I'm hopeful that it's only one bug fix away. The pre-release tasks are: * Fix the current bug * Test that Exupery can compile in the background for an hour * Check that the stress test still runs * Get Exupery installing from Package Universes * Build an Exupery development package on Package Universes * Integrate the 2G VM fixes from Dave and John. I'd like to make it easier to build Exupery development images, Exupery's development tools use more packages than Exupery needs to run. The two things that need to be done is automating the build and making sure that the catalogue has up to date pointers to to packages. Some packages still point to the old minnow location for the Squeak swiki. I'd also like to integrate the 2G unsigned pointer comparison fixes as they were causing crashes on my laptop after fixing the root table bugs. At the time, I thought it was image corruption which is plausible after debugging a GC related bug. Bryce

2 2

A new article about Exupery.
by bryce＠kampjes.demon.co.uk 19 Aug '07

19 Aug '07

I've added a new article about Exupery's design and direction to Exupery's bibliography. It's the last link on this page: http://wiki.squeak.org/squeak/5792 Bryce

1 0

Tagging
by Jason Johnson 04 Aug '07

04 Aug '07

Hello all, As I have mentioned before, I am thinking about creating a new VM for testing some of my ideas. One thing I noticed in the blue book was the tagging they use on the first (least significant) bit. By doing this you always have to shift the number before you can work with it. My thought was moving the tag to the last bit (most significant) and making 0 mean SmallPositiveInteger and 1 for OOP's. This way, once the number is identified to be a number nothing more need be done to use it and it doesn't need to be converted to be put back. As far as negative numbers, if I use a 31 bit header for my OOPS then the first bit of the header can be a flag. If the flag is 1 it's actually a negative number, otherwise it's a normal header. To clarify what I mean, here are some examples (first half byte in binary, rest in hex) 0000-0 00 00 ff - SmallPositiveInteger(255) 0111-f ff ff ff - SmallPositiveInteger(2147483647) 1xxx-x xx xx 01 - OOP(random memory address) 1xxx-x xx xx 02 - OOP(random memory address) 1xxx-x xx xx 03 - OOP(random memory address) (at address 0xxx-x xx xx 01) 1000-0 00 00 00 - SmallNegativeInteger(-2147483647) (at address 0xxx-x xx xx 02) 1111-f ff ff ff - SmallNegativeInteger(-1) (at address 0xxx-x xx xx 03) 0xxx-x xx xx xx - OO Header for a regular object So does anyone know any problems with this approach that make it unusable/unpractical? The only things I see are: 1) This representation is tied to 2's compliment, but are there any system that don't use that? 2) This system can only deal with 2 gigs worth of address pointers (can be hard coded to high or low but not both). How does any Smalltalk get around this? 3) Negative numbers require indirect memory access. Are negative numbers used so much this would be a problem? If so, one option would be to switch from 31 bits to 30 and use 2 bits for the tag (00 = SmallPositiveInteger, 11 = SmallNegativeInteger, 01 = Float?) I think VW is using two tag bits. 4) By tagging on the high side I have no option of using a value less then 32 bits (e.g. an 8-byte char). Perhaps characters can be done as my initial negative number solution as well by having a special OO header to represent them. Since the pointer points to the top, not the bottom maybe the header could be variable size (i.e. less then 32 bits). So what do you all think? Any big problems I didn't mention? Or solutions to the problems I mentioned? Or papers about this kind of thing (since my google-fu has not found too much on the subject so far)? Thanks in advance, Jason

3 4

Re: Your ASM generator
by Igor Stasenko 01 Aug '07

01 Aug '07

I CCed our discussion to exupery board. Want to hear what Bryce thinks too :) On 31/07/07, Jason Johnson <jason.johnson.081(a)gmail.com> wrote: > > > On 7/31/07, Igor Stasenko <siguctua(a)gmail.com> wrote: > > On 31/07/07, Jason Johnson <jason.johnson.081(a)gmail.com> wrote: > > > > Not at all! Idea is good. I didn't seen a need for macros - as you may > > know i'm focused on using code inlining. In most cases with use of > > inlining we can achieve same results as with macros , because inlining > > have same semantics: expand inlined code at call place. > > > But does it evaluate it first? One popular example from Paul Grahams Common > Lisp book is a macro called "random_choice". You call it like: > > (let direction (random_choice (:east :west :north :south))) > > And what actually gets expanded into the code is like: > > (let direction (condition (random 4) > ((1) (:east)) > ((2) (:west)) > ((3) (:north)) > ((4) (:south)))) > > That is, the compiler sees the use of the macro, calls it with the options > given, the random_choice macro looks at the number of arguments it received, > outputs a call to random for that number and sets up the conditions so that > each possible number will pick one of the choices. So it's better then what > I know as inlining, it allows you to use functions (built in, or what you > have written) to make writing new code more concise and clear without the > runtime overhead of functions. > >From that point , writing: 'register message' is same thing as macro, but its evaluated in smalltalk code for generating an intermediate form. For example i can add a #toSmallInt selector, so writing: reg toSmallInt will lead to generate following intermediate: sal reg 1 inc reg Lambda argument replacement can be done in smalltalk code (just by writing new method in AsmSelectors), everything else can be done using inlining. I agree, this is not so elegant as lisp macros, because you need to write code in different domains to get what you want. > > > I planned to make calling conventions support as hard-coded feature, > > but now i see, that by using macros it can be implemented on asm > > (using some special syntax), except one thing: how to tell compiler > > that upon return , the result will be stored in CPU register (eax for > > x86), so it will know how to deal with result later? > > > I had planned to have a different macro for defining functions depending on > how they behave. For example, if wanted to create functions that can be > called from C code we might define them with: > > (def-c-function myCfunction (...)) "has cdecl > > Returning via eax would probably be the default: > > (def myFunctionReturnsFromEAX (...)) > > With a stack: > > (def-stack-function my-stack-function (...)) > etc. > > > > Some of your ideas interfere with Exupery. They will need a more > > advanced assembler compiler than Exupery currently have to make some > > things doable :) > > > > What parts will be problem areas? > Ironically, but Exupery have printable intermediate forms which already looks like a lisp code: #(#(#block 1 #(#push #ebp) #(#mov #esp #ebp)) #(#block 3 #(#mov #(-4 #ebp) #eax) #(#mov #(-8 #ebp) #ebx)) #(#block 5 #(#sub #ebx #eax)) #(#block 4) #(#block 6) #(#block 2 #(#mov #ebp #esp) #(#pop #ebp) #(#ret))) - remove '#' and see what we got :) Exupery already having a number of optimizers which manipulating with intermediate. I think that for getting full potential of lisp macros/optimization schemes you will need to implement them on lisp. > > I liked your idea of using macros. Just one thing: i want to stick > > with smalltalk syntax. Because of 2 things: > > - introducing new syntax will require to implement own parser > > > Parser no, there is already a Lisp parser called Lisp kit. It will handle > the parsing and the common lisp example will have the macro handling in it. > So it would just be mostly a matter of defining lisp macros for what we want > and defining the primitives to be the assembly intermediate. > > > - using other than smalltalk syntax will scare off potential > > developers, who write on smalltalk and don't want to hear about > > anything else ;) > > > That's possible, though I'm not as concerned about it. Some will like both > (as I do) and it will open the door to new people as well. Plus, one > usually goes to lisp so they don't have to have such a big development team, > just as they do in Smalltalk. :) > Also, consider that smalltalk have more readable syntax than any programming language i have managed to learn during my more than 20 years of programming experience, including Lisp :) > > I'm sure we can deal with everything just fine by using smalltalk > > syntax. Just need to formalize some things. > > In fact, all my syntax based on executing code in single class with > > same selector as used in asm. > > So, when you put 'a+b' in asm code, this leads to call AsmSelectors>>+ > > method which generates corresponding intermediate for this operation. > > Well, you can still have macros in Smalltalk (though it's hard to do with > Squeak's compiler if you want to use ##). What Dolphin does already, and I > have seen patches for VW is to override ##() to be a macro. You can write > pure smalltalk code and the output is placed in the location the macro was > before the compile is completed. > I never programmed in Lisp, so i can't say how its easy/hard to implement a compiler and define a set of functions for writing assembler code. -- Best regards, Igor Stasenko AKA sig.

1 0

RE: Dynamically choosing a register
by J J 30 Jul '07

30 Jul '07

> From: bryce(a)kampjes.demon.co.uk> Date: Thu, 26 Jul 2007 11:43:43 +0100> To: exupery(a)lists.squeakfoundation.org> Subject: RE: Dynamically choosing a register> > > Do you mean for the cond to be evaluated at compile time in the> following?> > (def store-to-register (reg val)> (cond (reg)> ((number-that-means-eax) (store eax val)No, it can't be compile time since val will live in a field in instances of MethodContext. I can't know what val is until runtime. What I really want is a way to store in memory or another register some kind of reference to a register so that I would have the option in my VM that a caller can request the answer put right into the literal register of his choice.> If so you could just generate:> (mov t1 eax)> > Then the register allocator will try to allocate t1 in eax> and remove that move.> > BryceIs there any documentation on your mid and low level code generator? I would like to make a lisp-like language that targets it. This way I wouldn't have to make a compiler for every processor type, but I would have full power of the CPU and no dependencies on C. _________________________________________________________________ See what you’re getting into…before you go there. http://newlivehotmail.com

3 2

RE: Dynamically choosing a register
by J J 26 Jul '07

26 Jul '07

> Date: Tue, 24 Jul 2007 20:37:12 +0300> From: siguctua(a)gmail.com> To: exupery(a)lists.squeakfoundation.org> Subject: Re: Dynamically choosing a register> > as i understood, you want to do similar by telling a send oop, where> to store a result.> well, you may point to stack index, or point to address of memory with> given stack index.> but i'm unsure, is stack in squeak are subject for GC relocations. if> so, then better use index rather than pointers.Ok, I sent this mail in a rush because I didn't want to still be on the train when it left my station, so I figured it wouldn't end up making sense. :)What I mean is, right now MethodConext's have various fields in them (BlockContexts as well, but they point to MethodContexts for most information). What I was thinking of doing was adding an addition field "returnLocation". This way the compiler can simply ensure the value that is to be returned stores it's value to that area directly.Example (I means instance variable location, O means Object for the general purpose registers, S is a special and L is the literal frame):center ^ origin + corner / 2might be translated to:send2 #+ I1 I2 O1 ; Send the message #+ with the first instance slot as the receiver (first object) and the second instance slot as the argument. Store results in GP register O1send2 #/ O1 S(2) RET ; Send #/ with O1 as the receiver and the special number 2 as the argument. store the result into what ever place *our caller* expects it to be storedret ; Destroy this context and reactivate the previous oneSo note above that when the receiver in O1 receives the #/ message the RET field in *his* activation context will be the same as *ours (i.e. center's)*. So when he stores the answer we don't have to do anything, as it is in the right place already.The complexity comes from the fact that RET might be an instance variable, a temp variable location, a GP register *or* it may be an actual hardware register. But I'm not sure if that's even doable without making self-modifying code, which lead to my question: Can I have some value that I pass around dynamically that "points" to a hardware register?I can easily have a special encoding that says "the 3rd general purpose hardware register" or even the literal x86 value that maps to e.g. "eax", but how would one use this value at runtime? C, et al don't have this problem because the compiler explicitly states what values are going into which registers at build time. I have never heard of passing around a register "address".Of course I could do something like (note: the following pseudo code is intended to be a low level lisp-like language that compiles directly to machine code):(def store-to-register (reg val) (cond (reg) ((number-that-means-eax) (store eax val) .....But if it's going to be the expensive I may as well just store into memory. I was hoping I could do something like (example in pseudo assembly this time):movRegAt %ebx, $val ; the ebx register somehow has a reference to another register and stores $val there instead of ebx or memory or anywhere else.I suppose, since I have to have different functions for each addressing mode anyway, I can just have the routine that detects the type overwrite the register in the register store routine directly every time. :)Hopefully that makes a little more sense. :)Thanks,Jason _________________________________________________________________ Don't get caught with egg on your face. Play Chicktionary! http://club.live.com/chicktionary.aspx?icid=chick_wlmailtextlink

3 2

Dynamically choosing a register
by J J 24 Jul '07

24 Jul '07

Hello list,I have a question that is probably silly, but I couldn't find anything on the internet that answered it exactly.I am looking at a register machine version of Squeak, and one thought I had to make the number of operations per method even less was that the send opcode would put the location that the result should be stored into a variable in the new active context.My question was, in some cases I would like this to be a literal hardware, but is that even possible? Do all register names have to already be in code or can a memory location refer to a register and the CPU use it (e.g. x86store_op [some memory location that points to a register] ; double indirection)?Thanks,Jason _________________________________________________________________ PC Magazine’s 2007 editors’ choice for best web mail—award-winning Windows Live Hotmail. http://imagine-windowslive.com/hotmail/?locale=en-us&ocid=TXT_TAGHM_migrati…

2 1

RE: Asm-Generator - integration with Compiler
by J J 23 Jul '07

23 Jul '07

> Date: Fri, 13 Jul 2007 08:57:08 +0300> From: siguctua(a)gmail.com> To: exupery(a)lists.squeakfoundation.org> Subject: Asm-Generator - integration with Compiler> > To indicate that currently submitted method is assembler, developer> just need to put> <assembler> pragma in code.> I will place some 'awful hacks' in Compiler to react on this pragma> and redirect all further processing to my classes.Alternatively, you can just add a class side method (#compilerClass I think it is) that tells Smalltalk to use what ever class you want when it tries to compile methods for the class. This might be better "self documenting" for people reading the code that aren't familiar with what <assembler> might mean and wouldn't know where too look. But if they see compilerClass then they know exactly what class to look at to see what's going on. _________________________________________________________________ Local listings, incredible imagery, and driving directions - all in one place! Find it! http://maps.live.com/?wip=69&FORM=MGAC01

3 3

VM pointers delivered
by sig 22 Jul '07

22 Jul '07

VMMaker-sig.70 Exupery-sig.262 - removed numerous xxxxAddress methods from Interpreter, ExuperyPlugin, MachineX86. - added 4 new methods to Interpreter: exuperyPrimitiveGlobalPtrCount -- returns number of pointers stored in table exuperyPrimitiveGlobalPtrByName -- by giving a name of pointer (string or symbol) returns an array (pointer name proto) , or nil if not found exuperyPrimitiveGlobalPtrByIndex -- same as above but uses index as parameter exuperyGetGlobalPtrInfo: -- helper function to generate Array (pointer name proto) To see all VM global pointers use Exupery vmGlobalPtrs will return dictionary name -> info. where info is array of 4 elements: - pointer value - name - prototype for functions or '<var>' for variables a function prototype can be useful to see argument types and names e.t.c., so, it can be parsed in smalltalk to generate a cdecl callout to it. - index in global table ( left for later use , when i add support for replacing pointer in table :) ) also, note, the function names are stored as smalltalk selectors, not their corresponding C equivalents. so, you have names like 'commonVariableInternal:at:cacheIndex:' instead of 'commonVariableInternalatcacheIndex' in table so its easier to get to its implementation in Interpreter class. To see, how globals table generated look at CCodeGenerator>>emitGlobalTablesOn:methodList: i'm using struct instead of array, to preserve function names and type info. so later i can substitute calls like: foo(bar) with VMPointers->foo(bar) and then be able to replace given function with anything i want. All tests is passed fine except 3 cases, simply because i don't have following classes in image: GraphVizBaseTests CommandShell FloatMathPluginTests i don't think something will change if they will be. :)

2 5

[Draft Article] Optimizing Contexts
by Matthew Fulmer 14 Jul '07

14 Jul '07

Cross-posted to: strongtalk-general(a)googlegroups.com vm-dev(a)lists.squeakfoundation.org exupery(a)lists.squeakfoundation.org news(a)lists.squeakfoundation.org comp.lang.smalltalk Hello lists. This is a draft of an article I am writing for an upcoming series at the Weekly Squeak. It is about optimizing context creation, I would like comments on its technical correctness, as well as suggestions for related content I should include. I would especially like to know if this article covers the way this is handled in systems I did not specifically research, such as Strongtalk, and Exupery, and non-smalltalk systems like Common Lisp, Erlang, Haskell, and OCaml, since this topic is not really specific to object-oriented systems. This will not be the first article of the series; however, the first two paragraphs are the preliminary series introduction. I put them in so that you can get an idea of what I am writing. Sections enclosed in ... tags are parts I am especially unsure of; I would appreciate comments (I used i tags, because my editor, vim, highlights the enclosed text when in HTML mode). Look forward to this appearing in the Weekly Squeak: http://news.squeak.org/ Thank you for your help, and enjoy the article! === Speeding Up Smalltalk Series, part 42: Context Optimizations === Ever since object-oriented systems became popular, they have had the image of being very easy to program, but very slow in terms of execution speed. This image and reality has plagued every popular object-oriented system, starting with Smalltalk in the 80's and continuing on to Java and Ruby today. However, this does not have to be the case. Early-bound languages have gotten much faster thanks to lots of research on compilers and computer architecture. Similarly, much research has been done on making late-bound object-oriented systems fast, both with software and with hardware. This research has not seen as much exposure as processor research, and so is probably less familiar to you. This series, "Speeding Up Smalltalk" attempts to summarize a lot of that research and present it for your enjoyment. Computation in Smalltalk and Self is done by sending messages to objects. This seemingly simple operation of sending a message is done so often and is so flexible that it is always the execution bottleneck in any implementation of Smalltalk or similar object-oriented system. Why is that? ---- Description of Context Objects ---- Every time a message is sent, four things happen: - A search is done through the message receiver for a method that has been sent. This was the topic of the previous article, and will not be discussed here. - A context object is allocated on the heap. - The context object is initialized and filled with: - local objects, including: - pointers to the message arguments - pointers for each local variable - pointers for temporary storage needed for intermediate results - A way to reference variables defined in other scopes. This is a property blocks have, but methods don't - In Smalltalk, by a pointer to the "home context" - In Self, by delegate slots to the enclosing context(s) - A return address at which to resume execution - Squeak does not need this, since every context has it's own PC, so when returning, the PC of the returned-to context is already in the right place. This is equivalent to a return address, since a child's return address is the parents PC. - A return context that will become current upon return - The newly-created context is made the "current" context for this thread/process In Squeak, MethodContexts and BlockContexts are subclasses of ContextPart. ContextPart has three instance variables: - sender: The context that sent the message being executed. This context will become current when the current context returns - pc: A pointer to the currently executing instruction - stackp: The pointer to the execution stack. The smalltalk virtual machine is a stack processor. local variables are stored in the indexed fields of the context. stackp keeps track of which OOP is at the top of the stack. For MethodContexts: MethodContext extends it with 3 instance variables, and a variable-sized area for holding the temporaries: - method: the CompiledMethod holding the code being executed - receiverMap: Something to do with the names of the variables. Not really sure - receiver: a pointer to "self", the receiver of the message. ---- Squeak optimization: Static Contexts ---- In Squeak, BlockContexts are partial closures (sometimes called static blocks/closures [3]). Rather than hold their own code and environment, BlockContexts piggyback off of another context/code pair. Home is the environment that the block piggybacks off of. This usually works, but there are some cases where this scheme will not work: - like what? Why not? I don't understand why this doesn't always work. Something to do with re-entrancy or circular references. Not sure why either is a problem. For BlockContexts: - nargs: the number of arguments that the block must be called with. - startpc: The index into <code>self home method</code> where the code for the block starts. - home: the home environment Squeak's NewCompiler has a different representation of blocks. These are full closures, storing their own code and environment. They are sometimes called dynamic closures to distinguish them from the above "static closures" [3]. They contain: - method: The code of the block (CompiledMethod2) - environment: Captured temps (ClosureEnvironment) ---- Squeak optimization: Context Recycling ---- To avoid having to create a new MethodContext on every message send, Squeak keeps a pool of pre-allocated MethodContexts, and simply fills one up when a new one is needed. To support this optimization, MethodContexts are only created with two sizes, rather than any size that they could support. The small size has room for a few temporaries, and the large size has room for a bunch [4] ---- VisualWorks optimization: Context Caches ---- The most natural way to store contexts is as a linked list of objects, but that does not map well to the hardware of many processors. Many processors (including all the Intel varieties) have several built-in instructions to mechanize the creation of stack frames, which are similar to context objects, but have several important differences. VisualWorks uses these native stack frames for most operations, meaning that context creation is identical to a C function send in many cases. Thus, the hardware stack acts as a stand-in for the context objects; this optimization is called a context cache. However, stack frames cannot handle context responsibilities beyond a single call and return; when more is needed, a context object must be allocated on the heap. The context object can either be a context in it's own right (a stable context), or act as a proxy to the hardware stack frame (hybrid context). There are several complications to this dual scheme; curious readers should refer to [5]. VW and Squeak does not use a stack of context frames; instead it uses a linked list of real context objects. This is easier, but perhaps slower. To save on allocation costs, contexts are cached and recycled for various method invocations. Not sure where to incorporate this There are three types of blocks: - open/clean blocks (pure function with no closure) - copying blocks - full blocks ---- Or you can cheat... ---- The most popular object-oriented languages (C++, Java) chose to dump the flexibility of blocks in exchange for runtime speed. These languages use a native stack frame without providing the escape mechanism of a context cache, so that blocks and other context behavior that does not follow stack principles is not supported. This is a tradeoff that eliminates a good deal of flexibility, and so will not be explored further. ---- Final words ---- Inlining solves many of the same problems as a Context cache does. If the method body is inlined into the caller, no new context need be created. However, inlining solves many more problems than just context elimination; I will dedicate an entire article to it. ---- References ---- - context recycling may be discussed in tims nublue book: http://www.rowledge.org/tim/squeak/OE-Tour.html - context caches are discussed in section 5.2.3 of http://www.kampjes.demon.co.uk/articles/exuperyDesign.pdf [3] add reference to squeak mailing list or Ian's something to discuss the difference between static and dynamic closures [4] Squeak Class comments of <code>InstructionStream</code>, <code>ContextPart</code>, <code> MethodContext</code>. and <code>BlockContext</code>. [5]: Context Management in VisualWorks 5i: http://wiki.cs.uiuc.edu/VisualWorks/DOWNLOAD/papers/oopsla99-contexts.pdf -- Matthew Fulmer -- http://mtfulmer.wordpress.com/ Help improve Squeak Documentation: http://wiki.squeak.org/squeak/808

2 1

← Newer
1
2
3
4
5
6
7
8
...
11
Older →

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

Exupery