GitLab

Merge backend-hacking-branch onto HEAD.  Yay!

import fix

------------------------
       Tidy up the code generator
	------------------------

The code generation for 'case' expressions had grown
huge and gnarly.  This commit removes about 120 lines of
code, and makes it a lot easier to read too. I think the code
generated is identical.

Part of this was to simplify the StgCase data type, so
that it is more like the Core case: there is a simple list
of alternatives, and the DEFAULT (if present) must be the
first.  This tidies and simplifies other Stg passes.

Change the way SRTs are represented:

Previously, the SRT associated with a function or thunk would be a
sub-list of the enclosing top-level function's SRT.  But this approach
can lead to lots of duplication: if a CAF is referenced in several
different thunks, then it may appear several times in the SRT.
Let-no-escapes compound the problem, because the occurrence of a
let-no-escape-bound variable would expand to all the CAFs referred to
by the let-no-escape.

The new way is to describe the SRT associated with a function or thunk
as a (pointer+offset,bitmap) pair, where the pointer+offset points
into some SRT table (the enclosing function's SRT), and the bitmap
indicates which entries in this table are "live" for this closure.
The bitmap is stored in the 16 bits previously used for the length
field, but this rarely overflows.  When it does overflow, we store the
bitmap externally in a new "SRT descriptor".

Now the enclosing SRT can be a set, hence eliminating the duplicates.

Also, we now have one SRT per top-level function in a recursive group,
where previously we used to have one SRT for the whole group.  This
helps keep the size of SRTs down.

Bottom line: very little difference most of the time.  GHC itself got
slightly smaller.  One bad case of a module in GHC which had a huge
SRT has gone away.

While I was in the area:

  - Several parts of the back-end require bitmaps.  Functions for
    creating bitmaps are now centralised in the Bitmap module.

  - We were trying to be independent of word-size in a couple of
    places in the back end, but we've now abandoned that strategy so I
    simplified things a bit.

Update comments

Simplify the bitmap-generating code by collecting all the pointer
words rather than all the non-pointer words, and then subtracting
these from a bitmap made of all ones.  This is simpler because we only
have to look in the bindings, rather than combining information from
bindings and the free stack slot list.

Expand bitmaps to cover the full size of the stack frame.  Previously
the bitmap would stop at the last non-zero bit, which might shorten
the bitmap by one or more words.  The behaviour used to be correct,
but with the eval/apply changes bitmaps must now cover the entire
stack frame rather than everything up to the last non-pointer word.

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.

------------------------
	Change
		GlobalName --> ExternalName
		LocalName  ->  InternalName
	------------------------

For a long time there's been terminological confusion between

	GlobalName vs LocalName	 (property of a Name)
	GlobalId vs LocalId	 (property of an Id)

I've now changed the terminology for Name to be

	ExternalName vs InternalName

I've also added quite a bit of documentation in the Commentary.

We don't need to consider Hp as a volatile register across C calls; it
is already saved by the CALLER_SAVES_SYSTEM macro.

--------------------------
	Tidy up arity propagation (the saga continues)
	--------------------------

Turns out that it's not as easy as I thought.

The code generator was assuming that (not . isLocalName) was enough to
identify an imported thing (whose CgInfo should be right), but that's
not true.  Needs more thought.

Meanwhile, I've made the code generator a bit more sensible about how
it looks things up.  But there's still a problem for GHCi: the
unfoldings in the TypeEnv won't have CgIdInfo stuff.  Sigh.  Thinks.

wibble

merge (ghc-5-02-branch --> HEAD):

Bugfix: there was an implicit assumption that the list of slots passed
to freeStackSlots was already sorted, whereas in fact this wasn't the
case for at least one call.  Now we explicitly sort the list in
freeStackSlots, removing the hidden assumption.

The symptoms of this bug include crashes (perhaps the "AsmCodeGen"
crash), and a tendency to grow the stack a lot when let-no-escapes are
involved (because the bug caused fragmentation of the stack free list,
so we weren't re-using free slots properly).
  1.17.2.1  +3 -2      fptools/ghc/compiler/codeGen/CgStackery.lhs


ASSERT that the list of stack slots we calculate in buildLivenessMask
is sorted, because we rely on that property later.
  1.38.2.1  +5 -6      fptools/ghc/compiler/codeGen/CgBindery.lhs

Reapplied my "FCode as a monad" patch, now that 5.02 has forked into
a separate branch.

I'm fairly sure that this doesn't change the behaviour of anything.

Back out recent changes to the code generator as too destabilising.
Revert files as follows:

revert to 1.35   CgBindery.lhs
revert to 1.26   CgMonad.lhs
revert to 1.15   CgStackery.lhs
revert to 1.10   CgUsages.lhs

make it compile.

FCode/Code is now a monad, and thus now also a constructed type, rather than a
type synonym.

This requires quite a lot of changes in quite a lot of files, but none of these changes should have changed the behaviour of anything.

Being a Monad allows code that used FCode to be IMHO rather more readable
as it can use do notation, and other common Monad idioms.

In addition, state has been abstracted away with getter and setter
functions, so that functions mess with the innards of FCode as little as
possible - making it easier to change FCode in future.

Removed 32-bit dependencies in the generation and handling of
liveness mask bitmaps.  We now support both 32-bit and 64-bit
machines with identical .hc files.  Support for >64-bit machines
would be easy to add.  Note that old .hc files are incompatible
with the changes made to ghc/include/InfoMacros.h!

Re-engineer the transition from Core to STG syntax.  Main changes in
  this commit:

    - a new pass, CoreSat, handles saturation of constructors and PrimOps,
      and puts the syntax into STG-like normal form (applications to atoms
      only, etc), modulo type applications and Notes.

    - CoreToStg is now done at the same time as StgVarInfo.  Most of the
      contents of StgVarInfo.lhs have been copied into CoreToStg.lhs and
      some simplifications made.

  less major changes:

    - globalisation of names for the purposes of object splitting is
      now done by the C code generator (which is the Right Place in
      principle, but it was a bit fiddly).

    - CoreTidy now does cloning of local binders and collection of arity
      info.  The IdInfo from CoreTidy is now *almost* the final IdInfo we
      put in the interface file, except for CafInfo.  I'm going to move
      the CafInfo collection into CoreTidy in due course too.

    - and some other minor tidyups while I was in cluster-bomb commit mode.

Changing the way we know whether
something is exported.

THIS COMMIT WON'T EVEN COMPILE
(I'm doing it to transfer from my laptop.)
Wait till later today before updating.

Dealing with instance-decl imports; and removing unnecessary imports

remove unused imports; misc cleanup

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.

Crude allocation-counting extension to ticky-ticky profiling.

Allocations are counted against the closest lexically enclosing
function closure, so you need to map the output back to the STG code.

Move some code around to reduce the linkage between CgMonad and CgBindery,
and make the .hi-boot-5 file compatible with both 4.02 and 4.03.

Update the comment for buildLivenessMask to match reality.

Allow reserving of stack slots for non-pointer data (eg. cost
centres).  This means the previous hacks to keep the stack bitmaps
correct in the presence of cost centres are now unnecessary, and
case-of-case expressions will be compiled properly with profiling on.

Fix two uses of [ e1 .. e2 ] in light of the new Haskell 98 semantics.

Sort unboxed slots - part of the fix for large bitmaps.

Another big commit from Simon.  Actually, the last one
didn't all go into the main trunk; because of a CVS glitch it
ended up in the wrong branch.

So this commit includes:

* Scoped type variables
* Warnings for unused variables should work now (they didn't before)
* Simplifier improvements:
	- Much better treatment of strict arguments
	- Better treatment of bottoming Ids
	- No need for w/w split for fns that are merely strict
	- Fewer iterations needed, I hope
* Less gratuitous renaming in interface files and abs C
* OccName is a separate module, and is an abstract data type

I think the whole Prelude and Exts libraries compile correctly.
Something isn't quite right about typechecking existentials though.

Move 4.01 onto the main trunk.

Reorganisation of Id, IdInfo.  Remove StdIdInfo, PragmaInfo; add basicTypes/MkId.lhs

protect an import with #ifdef DEBUG.

The Great Multi-Parameter Type Classes Merge.

Notes from Simon (abridged):

* Multi-parameter type classes are fully implemented.
* Error messages from the type checker should be noticeably improved
* Warnings for unused bindings (-fwarn-unused-names)
* many other minor bug fixes.

Internally there are the following changes

* Removal of Haskell 1.2 compatibility.
* Dramatic clean-up of the PprStyle stuff.
* The type Type has been substantially changed.
* The dictionary for each class is represented by a new
  data type for that purpose, rather than by a tuple.

Move StableLoc (and assoc. access functions) from CgBindery to CgMonad. Done to avoid having to give the home of Maybe in CgBindery.hi-boot.

More small changes to 2.04

import updates

Updated to reflect move of PprStyle to Outputable

2.04 changes

Pragmas in interface files added