GitLab

No longer need them as temp vars in the cmm primop implementations.

This reduces the latency between a context-switch being triggered and
the thread returning to the scheduler, which in turn should reduce the
cost of the GC barrier when there are many cores.

We still retain the old context_switch flag which is checked at the
end of each block of allocation.  The idea is that setting HpLim may
fail if the the target thread is modifying HpLim at the same time; the
context_switch flag is a fallback.  It also allows us to "context
switch soon" without forcing an immediate switch, which can be costly.

Fixes crashes on Windows and Sparc

Eager blackholing can improve parallel performance by reducing the
chances that two threads perform the same computation.  However, it
has a cost: one extra memory write per thunk entry.  

To get the best results, any code which may be executed in parallel
should be compiled with eager blackholing turned on.  But since
there's a cost for sequential code, we make it optional and turn it on
for the parallel package only.  It might be a good idea to compile
applications (or modules) with parallel code in with
-feager-blackholing.

ToDo: document -feager-blackholing.

   Spark stealing support for PARALLEL_HASKELL and THREADED_RTS versions of the RTS.
  
  Spark pools are per capability, separately allocated and held in the Capability 
  structure. The implementation uses Double-Ended Queues (deque) and cas-protected 
  access.
  
  The write end of the queue (position bottom) can only be used with
  mutual exclusion, i.e. by exactly one caller at a time.
  Multiple readers can steal()/findSpark() from the read end
  (position top), and are synchronised without a lock, based on a cas
  of the top position. One reader wins, the others return NULL for a
  failure.
  
  Work stealing is called when Capabilities find no other work (inside yieldCapability),
  and tries all capabilities 0..n-1 twice, unless a theft succeeds.
  
  Inside schedulePushWork, all considered cap.s (those which were idle and could 
  be grabbed) are woken up. Future versions should wake up capabilities immediately when 
  putting a new spark in the local pool, from newSpark().

Patch has been re-recorded due to conflicting bugfixes in the sparks.c, also fixing a 
(strange) conflict in the scheduler.

This has several advantages:

 - -fvia-C is consistent with -fasm with respect to FFI declarations:
   both bind to the ABI, not the API.

 - foreign calls can now be inlined freely across module boundaries, since
   a header file is not required when compiling the call.

 - bootstrapping via C will be more reliable, because this difference
   in behavour between the two backends has been removed.

There is one disadvantage:

 - we get no checking by the C compiler that the FFI declaration
   is correct.

So now, the c-includes field in a .cabal file is always ignored by
GHC, as are header files specified in an FFI declaration.  This was
previously the case only for -fasm compilations, now it is also the
case for -fvia-C too.

ghc fails to build if you use an external gmp library. This is because
ghc requires the header file gmp.h, which used to be provided by the
internal gmp source code.  The file gmp.h is no longer part of the
gmp source code, but is generated as part of the build procedure.
If an external gmp is specified, the internal gmp is not build and the
gmp.h file never gets generated.

Of course, it was a bad idea anyway to use a header file from a potentially
different version of the library.

The patch sets HAVE_LIB_GMP if the gmp library is found during configuration
and conditionalizes including the library header file on it.

On OS X, we have to #include <GMP/gmp.h> if we are using GMP.framework. Before
the recent GMP changes, gcc (incorrectly) used the gmp.h supplied by ghc but
that is gone now. 

so that we can calculate deterministic offsets to some of the fields
of Capability.

Most of the other users of the fptools build system have migrated to
Cabal, and with the move to darcs we can now flatten the source tree
without losing history, so here goes.

The main change is that the ghc/ subdir is gone, and most of what it
contained is now at the top level.  The build system now makes no
pretense at being multi-project, it is just the GHC build system.

No doubt this will break many things, and there will be a period of
instability while we fix the dependencies.  A straightforward build
should work, but I haven't yet fixed binary/source distributions.
Changes to the Building Guide will follow, too.

Now, the threaded RTS also includes SMP support.  The -smp flag is a
synonym for -threaded.  The performance implications of this are small
to negligible, and it results in a code cleanup and reduces the number
of combinations we have to test.

We always assign to BaseReg on return from resumeThread(), but in
cases where BaseReg is not an lvalue (eg. unreg) we need to disable
this assigment.  See comments for more details.

Two improvements to the SMP runtime:

  - support for 'par', aka sparks.  Load balancing is very primitive
    right now, but I have seen programs that go faster using par.

  - support for backing off when a thread is found to be duplicating
    a computation currently underway in another thread.  This also
    fixes some instability in SMP, because it turned out that when
    an update frame points to an indirection, which can happen if
    a thunk is under evaluation in multiple threads, then after GC
    has shorted out the indirection the update will trash the value.
    Now we suspend the duplicate computation to the heap before this
    can happen.

Additionally:

  - stack squeezing is separate from lazy blackholing, and now only
    happens if there's a reasonable amount of squeezing to be done
    in relation to the number of words of stack that have to be moved.
    This means we won't try to shift 10Mb of stack just to save 2
    words at the bottom (it probably never happened, but still).

  - update frames are now marked when they have been visited by lazy
    blackholing, as per the SMP paper.

  - cleaned up raiseAsync() a bit.

- change the type of StgRun(): now we return the Capability that the
  thread currently holds.  The return status of the thread is now
  stored in cap->r.rRet (a new slot in the reg table).

  This was necessary because on return from StgRun(), the current
  TSO may be blocked, so it no longer belongs to us.  If it is a bound
  thread, then the Task may have been already woken up on another
  Capability, so the scheduler can't use task->cap to find the
  capability it currently owns.

- when shutting down, allow a bound thread to remove its TSO from
  the run queue when exiting (eliminates an error condition in
  releaseCapability()).

Fix build for way "u"

Big re-hash of the threaded/SMP runtime

This is a significant reworking of the threaded and SMP parts of
the runtime.  There are two overall goals here:

  - To push down the scheduler lock, reducing contention and allowing
    more parts of the system to run without locks.  In particular,
    the scheduler does not require a lock any more in the common case.

  - To improve affinity, so that running Haskell threads stick to the
    same OS threads as much as possible.

At this point we have the basic structure working, but there are some
pieces missing.  I believe it's reasonably stable - the important
parts of the testsuite pass in all the (normal,threaded,SMP) ways.

In more detail:

  - Each capability now has a run queue, instead of one global run
    queue.  The Capability and Task APIs have been completely
    rewritten; see Capability.h and Task.h for the details.

  - Each capability has its own pool of worker Tasks.  Hence, Haskell
    threads on a Capability's run queue will run on the same worker
    Task(s).  As long as the OS is doing something reasonable, this
    should mean they usually stick to the same CPU.  Another way to
    look at this is that we're assuming each Capability is associated
    with a fixed CPU.

  - What used to be StgMainThread is now part of the Task structure.
    Every OS thread in the runtime has an associated Task, and it
    can ask for its current Task at any time with myTask().

  - removed RTS_SUPPORTS_THREADS symbol, use THREADED_RTS instead
    (it is now defined for SMP too).

  - The RtsAPI has had to change; we must explicitly pass a Capability
    around now.  The previous interface assumed some global state.
    SchedAPI has also changed a lot.

  - The OSThreads API now supports thread-local storage, used to
    implement myTask(), although it could be done more efficiently
    using gcc's __thread extension when available.

  - I've moved some POSIX-specific stuff into the posix subdirectory,
    moving in the direction of separating out platform-specific
    implementations.

  - lots of lock-debugging and assertions in the runtime.  In particular,
    when DEBUG is on, we catch multiple ACQUIRE_LOCK()s, and there is
    also an ASSERT_LOCK_HELD() call.

What's missing so far:

  - I have almost certainly broken the Win32 build, will fix soon.

  - any kind of thread migration or load balancing.  This is high up
    the agenda, though.

  - various performance tweaks to do

  - throwTo and forkProcess still do not work in SMP mode

Update STM implementation for SMP builds

Two SMP-related changes:

  - New storage manager interface:

    bdescr *allocateLocal(StgRegTable *reg, nat words)

    which allocates from the current thread's nursery (being careful
    not to clash with the heap pointer).  It can do this without
    taking any locks; the lock only has to be taken if a block needs
    to be allocated.  allocateLocal() is now used instead of allocate()
    in a few PrimOps.

    This removes locks from most Integer operations, cutting down
    the overhead for SMP a bit more.

    To make this work, we have to be able to grab the current thread's
    Capability out of thin air (i.e. when called from GMP), so the
    Capability subsystem needs to keep a hash from thread IDs to
    Capabilities.

  - Small MVar optimisation: instead of taking the global
    storage-manager lock, do our own locking of MVars with a bit of
    inline assembly (x86 only for now).

The in_haskell sanity check should be per-Capability rather than global.

I just ran a Haskell program in 8 pthreads simultaneously :-)

Per-task nurseries for SMP.  This was kind-of implemented before, but
it's much cleaner now.  There is now one *step* per capability, so we
have somewhere to hang the block count.  So for SMP, there are simply
multiple instances of generation 0 step 0.  The rNursery entry in the
register table now points to the step rather than the head block of
the nurersy.

* Some preprocessors don't like the C99/C++ '//' comments after a
  directive, so use '/* */' instead. For consistency, a lot of '//' in
  the include files were converted, too.

* UnDOSified libraries/base/cbits/runProcess.c.

* My favourite sport: Killed $Id$s.

Make it so that global register declarations are turned off if
NO_GLOBAL_REG_DECLS is defined.

Merge backend-hacking-branch onto HEAD.  Yay!

Revert previous commit on request

Style police: Remove C++-style comments

Merge the eval-apply-branch on to the HEAD
------------------------------------------

This is a change to GHC's evaluation model in order to ultimately make
GHC more portable and to reduce complexity in some areas.

At some point we'll update the commentary to describe the new state of
the RTS.  Pending that, the highlights of this change are:

  - No more Su.  The Su register is gone, update frames are one
    word smaller.

  - Slow-entry points and arg checks are gone.  Unknown function calls
    are handled by automatically-generated RTS entry points (AutoApply.hc,
    generated by the program in utils/genapply).

  - The stack layout is stricter: there are no "pending arguments" on
    the stack any more, the stack is always strictly a sequence of
    stack frames.

    This means that there's no need for LOOKS_LIKE_GHC_INFO() or
    LOOKS_LIKE_STATIC_CLOSURE() any more, and GHC doesn't need to know
    how to find the boundary between the text and data segments (BIG WIN!).

  - A couple of nasty hacks in the mangler caused by the neet to
    identify closure ptrs vs. info tables have gone away.

  - Info tables are a bit more complicated.  See InfoTables.h for the
    details.

  - As a side effect, GHCi can now deal with polymorphic seq.  Some bugs
    in GHCi which affected primitives and unboxed tuples are now
    fixed.

  - Binary sizes are reduced by about 7% on x86.  Performance is roughly
    similar, some programs get faster while some get slower.  I've seen
    GHCi perform worse on some examples, but haven't investigated
    further yet (GHCi performance *should* be about the same or better
    in theory).

  - Internally the code generator is rather better organised.  I've moved
    info-table generation from the NCG into the main codeGen where it is
    shared with the C back-end; info tables are now emitted as arrays
    of words in both back-ends.  The NCG is one step closer to being able
    to support profiling.

This has all been fairly thoroughly tested, but no doubt I've messed
up the commit in some way.

SMP: move link field from StgRegTable to Capability

Fix the large block allocation bug (Yay!)
-----------------------------------------

In order to do this, I had to

 1. in each heap-check failure branch, return the amount of heap
    actually requested, in a known location (I added another slot
    in StgRegTable called HpAlloc for this purpose).  This is
    useful for other reasons - in particular it makes it possible
    to get accurate allocation statistics.

 2. In the scheduler, if a heap check fails and we wanted more than
    BLOCK_SIZE_W words, then allocate a special large block and place
    it in the nursery.  The nursery now has to be double-linked so
    we can insert the new block in the middle.

 3. The garbage collector has to be able to deal with multiple objects
    in a large block.  It turns out that this isn't a problem as long as
    the large blocks only occur in the nursery, because we always copy
    objects from the nursery during GC.  One small change had to be
    made: in evacuate(), we may need to follow the link field from the
    block descriptor to get to the block descriptor for the head of a
    large block.

 4. Various other parts of the storage manager had to be modified
    to cope with a nursery containing a mixture of block sizes.

Point (3) causes a slight pessimization in the garbage collector.  I
don't see a way to avoid this.  Point (1) causes some code bloat (a
rough measurement is around 5%), so to offset this I made the
following change which I'd been meaning to do for some time:

  - Store the values of some commonly-used absolute addresses
    (eg. stg_update_PAP) in the register table.  This lets us use
    shorter instruction forms for some absolute jumps and saves some
    code space.

  - The type of Capability is no longer the same as an StgRegTable.
    MainRegTable renamed to MainCapability.  See Regs.h for details.

Other minor changes:

  - remove individual declarations for the heap-check-failure jump
    points, and declare them all in StgMiscClosures.h instead.  Remove
    HeapStackCheck.h.

Updates to the native code generator to follow.

This utterly gigantic commit is what I've been up to in background
mode in the last couple of months.  Originally the main goal
was to get rid of Con (staturated constant applications)
in the CoreExpr type, but one thing led to another, and I kept
postponing actually committing.   Sorry.

	Simon, 23 March 2000


I've tested it pretty thoroughly, but doubtless things will break.

Here are the highlights

* Con is gone; the CoreExpr type is simpler
* NoRepLits have gone
* Better usage info in interface files => less recompilation
* Result type signatures work
* CCall primop is tidied up
* Constant folding now done by Rules
* Lots of hackery in the simplifier
* Improvements in CPR and strictness analysis

Many bug fixes including

* Sergey's DoCon compiles OK; no loop in the strictness analyser
* Volker Wysk's programs don't crash the CPR analyser

I have not done much on measuring compilation times and binary sizes;
they could have got worse.  I think performance has got significantly
better, though, in most cases.


Removing the Con form of Core expressions
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
The big thing is that

  For every constructor C there are now *two* Ids:

	C is the constructor's *wrapper*. It evaluates and unboxes arguments
	before calling $wC.  It has a perfectly ordinary top-level defn
	in the module defining the data type.

	$wC is the constructor's *worker*.  It is like a primop that simply
	allocates and builds the constructor value.  Its arguments are the
	actual representation arguments of the constructor.
	Its type may be different to C, because:
		- useless dict args are dropped
		- strict args may be flattened

  For every primop P there is *one* Id, its (curried) Id

  Neither contructor worker Id nor the primop Id have a defminition anywhere.
  Instead they are saturated during the core-to-STG pass, and the code generator
  generates code for them directly. The STG language still has saturated
  primops and constructor applications.

* The Const type disappears, along with Const.lhs.  The literal part
  of Const.lhs reappears as Literal.lhs.  Much tidying up in here,
  to bring all the range checking into this one module.

* I got rid of NoRep literals entirely.  They just seem to be too much trouble.

* Because Con's don't exist any more, the funny C { args } syntax
  disappears from inteface files.


Parsing
~~~~~~~
* Result type signatures now work
	f :: Int -> Int = \x -> x
	-- The Int->Int is the type of f

	g x y :: Int = x+y
	-- The Int is the type of the result of (g x y)


Recompilation checking and make
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* The .hi file for a modules is not touched if it doesn't change.  (It used to
  be touched regardless, forcing a chain of recompilations.)  The penalty for this
  is that we record exported things just as if they were mentioned in the body of
  the module.  And the penalty for that is that we may recompile a module when
  the only things that have changed are the things it is passing on without using.
  But it seems like a good trade.

* -recomp is on by default

Foreign declarations
~~~~~~~~~~~~~~~~~~~~
* If you say
	foreign export zoo :: Int -> IO Int
  then you get a C produre called 'zoo', not 'zzoo' as before.
  I've also added a check that complains if you export (or import) a C
  procedure whose name isn't legal C.


Code generation and labels
~~~~~~~~~~~~~~~~~~~~~~~~~~
* Now that constructor workers and wrappers have distinct names, there's
  no need to have a Foo_static_closure and a Foo_closure for constructor Foo.
  I nuked the entire StaticClosure story.  This has effects in some of
  the RTS headers (i.e. s/static_closure/closure/g)


Rules, constant folding
~~~~~~~~~~~~~~~~~~~~~~~
* Constant folding becomes just another rewrite rule, attached to the Id for the
  PrimOp.   To achieve this, there's a new form of Rule, a BuiltinRule (see CoreSyn.lhs).
  The prelude rules are in prelude/PrelRules.lhs, while simplCore/ConFold.lhs has gone.

* Appending of constant strings now works, using fold/build fusion, plus
  the rewrite rule
	unpack "foo" c (unpack "baz" c n)  =  unpack "foobaz" c n
  Implemented in PrelRules.lhs

* The CCall primop is tidied up quite a bit.  There is now a data type CCall,
  defined in PrimOp, that packages up the info needed for a particular CCall.
  There is a new Id for each new ccall, with an big "occurrence name"
	{__ccall "foo" gc Int# -> Int#}
  In interface files, this is parsed as a single Id, which is what it is, really.

Miscellaneous
~~~~~~~~~~~~~
* There were numerous places where the host compiler's
  minInt/maxInt was being used as the target machine's minInt/maxInt.
  I nuked all of these; everything is localised to inIntRange and inWordRange,
  in Literal.lhs

* Desugaring record updates was broken: it didn't generate correct matches when
  used withe records with fancy unboxing etc.  It now uses matchWrapper.

* Significant tidying up in codeGen/SMRep.lhs

* Add __word, __word64, __int64 terminals to signal the obvious types
  in interface files.  Add the ability to print word values in hex into
  C code.

* PrimOp.lhs is no longer part of a loop.  Remove PrimOp.hi-boot*


Types
~~~~~
* isProductTyCon no longer returns False for recursive products, nor
  for unboxed products; you have to test for these separately.
  There's no reason not to do CPR for recursive product types, for example.
  Ditto splitProductType_maybe.

Simplification
~~~~~~~~~~~~~~~
* New -fno-case-of-case flag for the simplifier.  We use this in the first run
  of the simplifier, where it helps to stop messing up expressions that
  the (subsequent) full laziness pass would otherwise find float out.
  It's much more effective than previous half-baked hacks in inlining.

  Actually, it turned out that there were three places in Simplify.lhs that
  needed to know use this flag.

* Make the float-in pass push duplicatable bindings into the branches of
  a case expression, in the hope that we never have to allocate them.
  (see FloatIn.sepBindsByDropPoint)

* Arrange that top-level bottoming Ids get a NOINLINE pragma
  This reduced gratuitous inlining of error messages.
  But arrange that such things still get w/w'd.

* Arrange that a strict argument position is regarded as an 'interesting'
  context, so that if we see
	foldr k z (g x)
  then we'll be inclined to inline g; this can expose a build.

* There was a missing case in CoreUtils.exprEtaExpandArity that meant
  we were missing some obvious cases for eta expansion
  Also improve the code when handling applications.

* Make record selectors (identifiable by their IdFlavour) into "cheap" operations.
	  [The change is a 2-liner in CoreUtils.exprIsCheap]
  This means that record selection may be inlined into function bodies, which
  greatly improves the arities of overloaded functions.

* Make a cleaner job of inlining "lone variables".  There was some distributed
  cunning, but I've centralised it all now in SimplUtils.analyseCont, which
  analyses the context of a call to decide whether it is "interesting".

* Don't specialise very small functions in Specialise.specDefn
  It's better to inline it.  Rather like the worker/wrapper case.

* Be just a little more aggressive when floating out of let rhss.
  See comments with Simplify.wantToExpose
  A small change with an occasional big effect.

* Make the inline-size computation think that
	case x of I# x -> ...
  is *free*.


CPR analysis
~~~~~~~~~~~~
* Fix what was essentially a bug in CPR analysis.  Consider

	letrec f x = let g y = let ... in f e1
		     in
		     if ... then (a,b) else g x

  g has the CPR property if f does; so when generating the final annotated
  RHS for f, we must use an envt in which f is bound to its final abstract
  value.  This wasn't happening.  Instead, f was given the CPR tag but g
  wasn't; but of course the w/w pass gives rotten results in that case!!
  (Because f's CPR-ness relied on g's.)

  On they way I tidied up the code in CprAnalyse.  It's quite a bit shorter.

  The fact that some data constructors return a constructed product shows
  up in their CPR info (MkId.mkDataConId) not in CprAnalyse.lhs



Strictness analysis and worker/wrapper
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* BIG THING: pass in the demand to StrictAnal.saExpr.  This affects situations
  like
	f (let x = e1 in (x,x))
  where f turns out to have strictness u(SS), say.  In this case we can
  mark x as demanded, and use a case expression for it.

  The situation before is that we didn't "know" that there is the u(SS)
  demand on the argument, so we simply computed that the body of the let
  expression is lazy in x, and marked x as lazily-demanded.  Then even after
  f was w/w'd we got

	let x = e1 in case (x,x) of (a,b) -> $wf a b

  and hence

	let x = e1 in $wf a b

  I found a much more complicated situation in spectral/sphere/Main.shade,
  which improved quite a bit with this change.

* Moved the StrictnessInfo type from IdInfo to Demand.  It's the logical
  place for it, and helps avoid module loops

* Do worker/wrapper for coerces even if the arity is zero.  Thus:
	stdout = coerce Handle (..blurg..)
  ==>
	wibble = (...blurg...)
	stdout = coerce Handle wibble
  This is good because I found places where we were saying
	case coerce t stdout of { MVar a ->
	...
	case coerce t stdout of { MVar b ->
	...
  and the redundant case wasn't getting eliminated because of the coerce.

Add 'par' and sparking support to the SMP implementation.

Fix up some problems with the IN_STG_CODE macro.

A slew of SMP-related changes.

 - New locking scheme for thunks: we now check whether the thunk
   being entered is in our private allocation area, and if so
   we don't lock it.  Well, that's the upshot.  In practice it's
   a lot more fiddly than that.

 - I/O blocking is handled a bit more sanely now (but still not
   properly, methinks)

 - deadlock detection is back

 - remove old pre-SMP scheduler code

 - revamp the timing code.  We actually get reasonable-looking
   timing info for SMP programs now.

 - fix a bug in the garbage collector to do with IND_OLDGENs appearing
   on the mutable list of the old generation.

 - move BDescr() function from rts/BlockAlloc.h to includes/Block.h.

 - move struct generation and struct step into includes/StgStorage.h (sigh)

 - add UPD_IND_NOLOCK for updating with an indirection where locking
   the black hole is not required.

This commit adds in the current state of our SMP support.  Notably,
this allows the new way 's' to be built, providing support for running
multiple Haskell threads simultaneously on top of any pthreads
implementation, the idea being to take advantage of commodity SMP
boxes.

Don't expect to get much of a speedup yet; due to the excessive
locking required to synchronise access to mutable heap objects, you'll
see a slowdown in most cases, even on a UP machine.  The best I've
seen is a 1.6-1.7 speedup on an example that did no locking (two
optimised nfibs in parallel).

	- new RTS -N flag specifies how many pthreads to start.

	- new driver -smp flag, tells the driver to use way 's'.

	- new compiler -fsmp option (not for user comsumption)
	  tells the compiler not to generate direct jumps to
	  thunk entry code.

	- largely rewritten scheduler

	- _ccall_GC is now done by handing back a "token" to the
	  RTS before executing the ccall; it should now be possible
	  to execute blocking ccalls in the current thread while
	  allowing the RTS to continue running Haskell threads as
	  normal.

	- you can only call thread-safe C libraries from a way 's'
	  build, of course.

Pthread support is still incomplete, and weird things (including
deadlocks) are likely to happen.

- misc changes to support DLLs
- StgNat* --> StgWord*

Copyright police.

Move 4.01 onto the main trunk.