From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII X-Google-Thread: 107f24,6f568a2e6507575 X-Google-Attributes: gid107f24,public X-Google-Thread: f891f,6f568a2e6507575 X-Google-Attributes: gidf891f,public X-Google-Thread: 103376,6f568a2e6507575 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2001-04-26 07:23:26 PST Path: newsfeed.google.com!newsfeed.stanford.edu!news.tele.dk!195.25.12.36!oleane.net!oleane!isdnet!news.internetia.pl!news.tpi.pl!nnrpd From: qrczak@knm.org.pl (Marcin 'Qrczak' Kowalczyk) Newsgroups: comp.lang.ada,comp.lang.functional,comp.lang.misc Subject: Re: Thoughts and Opinions or something like that Followup-To: comp.lang.functional Date: 26 Apr 2001 14:22:24 GMT Organization: Klub Nieszkodliwych =?iso-8859-2?Q?Manjak=F3w?= Message-ID: References: <3AE67F57.722A78D8@andrewcooke.free-online.co.uk> NNTP-Posting-Host: pm158.warszawa.cvx.ppp.tpnet.pl Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-2 Content-Transfer-Encoding: 8bit X-Trace: news.tpi.pl 988295083 7797 213.76.108.158 (26 Apr 2001 14:24:43 GMT) X-Complaints-To: usenet@tpi.pl NNTP-Posting-Date: 26 Apr 2001 14:24:43 GMT X-Orig-Path: localhost!qrczak User-Agent: slrn/0.9.6.3 (Linux) Xref: newsfeed.google.com comp.lang.ada:6956 comp.lang.functional:5329 comp.lang.misc:1153 Date: 2001-04-26T14:24:43+00:00 List-Id: Followup-To: comp.lang.functional Wed, 25 Apr 2001 11:42:02 +0100, chris.danx pisze: > I don't understand what you mean by "coroutines" but i assume from > what comes next it's got something to do with multiple stacks. > I suppose i could try something like having more than one SP in > the RISC version and see how that goes. Pop S2, for pop stack 2. > Or more generically Pop An, where An is an address register pointing > to the stack. Then i could integrate more a specific, better design > in the WillowVM (VM version 2). I guess that coroutines don't need the model when each stack operation names the stack - it is not known locally which stacks will be in use - but the ability to switch stacks, where each thread has its stack. > This is something i never got my head round. I get primitive > recusion, which involves just recurring a function (e.g. a factorial > function), but i know this is innefficient. Tail recursion has to > do with finishing the computution before calling another smaller > version of the computation. This means the system can use the same > frame over for the function i think? Glasgow Haskell Compiler uses tail calls exclusively. "Normal" calls where the caller wants to process the value returned by the callee before returning it are expressed as tail calls with the continuation as a parameter. Generally, since Haskell is lazy, an important operation is evaluation of an object. This is unified with applying a function. It is performed by jumping to the first word of the object. This is a jump without return. The "what to do next" pointer is passed as one of arguments. When a source function wants to perform evaluation of multiple objects, its code is physically split into pieces between evaluations. Each evaluation is passed the address of the next piece, except the last which is passed the "what to do next" pointer which our caller gave us. GHC almost doesn't use the system stack. It manages its own stack for passing arguments and return values, which grows and shrinks independently of the calling sequence. There is some gcc magic to keep stack and heap pointers in registers. This model is quite different from C-style calls with return address on the stack, so there are various hacks to implement it on different backends. This is for C backends (assembler code generated by the C compiler is later mangled which includes erasing some stuff): /* ----------------------------------------------------------------------------- * $Id: TailCalls.h,v 1.7 2001/02/14 10:33:05 simonmar Exp $ * * (c) The GHC Team, 1998-1999 * * Stuff for implementing proper tail jumps. * * ---------------------------------------------------------------------------*/ #ifndef TAILCALLS_H #define TAILCALLS_H /* ----------------------------------------------------------------------------- Unmangled tail-jumping: use the mini interpretter. -------------------------------------------------------------------------- */ #ifdef USE_MINIINTERPRETER #define JMP_(cont) return(stgCast(StgFunPtr,cont)) #define FB_ #define FE_ #else /* ----------------------------------------------------------------------------- Tail calling on x86 -------------------------------------------------------------------------- */ #if i386_TARGET_ARCH extern void __DISCARD__(void); /* Note about discard: possibly there to fool GCC into clearing up before we do the jump eg. if there are some arguments left on the C stack that GCC hasn't popped yet. Also possibly to fool any optimisations (a function call often acts as a barrier). Not sure if any of this is necessary now -- SDM Comment to above note: I don't think the __DISCARD__() in JMP_ is necessary. Arguments should be popped from the C stack immediately after returning from a function, as long as we pass -fno-defer-pop to gcc. Moreover, a goto to a first-class label acts as a barrier for optimisations in the same way a function call does. -= chak */ /* The goto here seems to cause gcc -O2 to delete all the code after it - including the FE_ marker and the epilogue code - exactly what we want! -- SDM */ #define JMP_(cont) \ { \ void *target; \ __DISCARD__(); \ target = (void *)(cont); \ goto *target; \ } #endif /* i386_TARGET_ARCH */ /* ----------------------------------------------------------------------------- Tail calling on Sparc -------------------------------------------------------------------------- */ #ifdef sparc_TARGET_ARCH #define JMP_(cont) ((F_) (cont))() /* Oh so happily, the above turns into a "call" instruction, which, on a SPARC, is nothing but a "jmpl" with the return address in %o7 [which we don't care about]. */ /* Don't need these for sparc mangling */ #define FB_ #define FE_ #endif /* sparc_TARGET_ARCH */ /* ----------------------------------------------------------------------------- Tail calling on Alpha -------------------------------------------------------------------------- */ #ifdef alpha_TARGET_ARCH register void *_procedure __asm__("$27"); #define JMP_(cont) \ do { _procedure = (void *)(cont); \ goto *_procedure; \ } while(0) /* Don't need these for alpha mangling */ #define FB_ #define FE_ #endif /* alpha_TARGET_ARCH */ /* ----------------------------------------------------------------------------- Tail calling on HP Description of HP's weird procedure linkage, many thanks to Andy Bennet : I've been digging a little further into the problem of how HP-UX does dynamic procedure calls. My solution in the last e-mail inserting an extra 'if' statement into the JMP_ I think is probably the best general solution I can come up with. There are still a few problems with it however: It wont work, if JMP_ ever has to call anything in a shared library, if this is likely to be required it'll need something more elaborate. It also wont work with PA-RISC 2.0 wide mode (64-bit) which uses a different format PLT. I had some feedback from someone in HP's compiler lab and the problem relates to the linker on HP-UX, not gcc as I first suspected. The reason the 'hsc' executable works is most likely due to a change in 'ld's behaviour for performance reasons between your revision and mine. The major issue relating to this is shared libraries and how they are implented under HP-UX. The whole point of the Procedure Label Table (PLT) is to allow a function pointer to hold the address of the function and a pointer to the library's global data lookup table (DLT) used by position independent code (PIC). This makes the PLT absolutely essential for shared library calls. HP has two linker introduced assembly functions for dealing with dynamic calls, $$dyncall and $$dyncall_external. The former does a check to see if the address is a PLT pointer and dereferences if necessary or just calls the address otherwise; the latter skips the check and just does the indirect jump no matter what. Since $$dyncall_external runs faster due to its not having the test, the linker nowadays prefers to generate calls to that, rather than $$dyncall. It makes this decision based on the presence of any shared library. If it even smells an sl's existence at link time, it rigs the runtime system to generate PLT references for everything on the assumption that the result will be slightly more efficient. This is what is crashing GHC since the calls it is generating have no understanding of the procedure label proper. The only way to get real addresses is to link everything archive, including system libraries, at which point it assumes you probably are going to be using calls similar to GHC's (its rigged for HP's +ESfic compiler option) but uses $$dyncall if necessary to cope, just in case you aren't. -------------------------------------------------------------------------- */ #ifdef hppa1_1_hp_hpux_TARGET #define JMP_(cont) \ do { void *_procedure = (void *)(cont); \ if (((int) _procedure) & 2) \ _procedure = (void *)(*((int *) (_procedure - 2))); \ goto *_procedure; \ } while(0) #endif /* hppa1_1_hp_hpux_TARGET */ /* ----------------------------------------------------------------------------- FUNBEGIN and FUNEND. These are markers indicating the start and end of Real Code in a function. All instructions between the actual start and end of the function and these markers is shredded by the mangler. -------------------------------------------------------------------------- */ /* The following __DISCARD__() has become necessary with gcc 2.96 on x86. * It prevents gcc from moving stack manipulation code from the function * body (aka the Real Code) into the function prologue, ie, from moving it * over the --- BEGIN --- marker. It should be noted that (like some * other black magic in GHC's code), there is no essential reason why gcc * could not move some stack manipulation code across the __DISCARD__() - * it just doesn't choose to do it at the moment. * -= chak */ #ifndef FB_ #define FB_ __asm__ volatile ("--- BEGIN ---"); __DISCARD__ (); #endif #ifndef FE_ #define FE_ __asm__ volatile ("--- END ---"); #endif #endif /* !USE_MINIINTERPRETER */ #endif /* TAILCALLS_H */ -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZAST�PCZA QRCZAK