WebHome
- UHC
- EHC
- Documentation
- Features & Status
- EH examples
- Feedback
- News
- FAQ

Related
- Ruler
- Shuffle
- uulib & uuagc

Old Stuff
- Previous WebHome
- AFP2004

Center
Master Program

Ehc Technical Documentation

Ehc

1 Core

1.1 Transformations per module

The following transformations are performed on each separate module:

EtaRed:
RenUniq:
LetUnrec:
InlineLetAlias:
ElimTrivApp:
ConstProp:
InlineLetAlias (again):
ElimTrivApp (again):
ANormal: The full lazy transformation gives names to argument subexpressions of an application. The purpose is to end up with bindings which (later) directly correspond to a CAF or a closure. For that to work, all arguments of an application closure must themselves be bound to names, i.e. be closures themselves.
LamGlobalAsArg:
CAFGlobalAsArg:
LetUnrec (again):
FullLazy (again):
FloatToGlobal:

1.2 Full program transformations

The following transformations are performed on the full program:

LiftDictFields:

2 GrinCode

2.1 Transformations per module

The following transformations are performed on each separate module:

(only when compiling to bytecode) UnusedMetaInfoElim:
Remove the annotations of values and lambda-patterns that are not necessary for the bytecode backend.
(only when compiling to bytecode) MayLiveUnboxed:
Values are all represented by nodes, boxed thus. This transformation removes the boxing for unboxable values, allowing direct manipulation.
Although designed with use by GrinByteCode in mind, the transformation is parameterised with a function telling whether a node represents an unboxed value.
(only when optimizing flag is on) FlattenSeq: (seems not useful here)
(only when optimizing flag is on) AliasElim:
Remove bindings of names to names. When directly executed absence of this transformation would lead to additional loads.
(only when optimizing flag is on) EvalElim:
Eliminate unnecessary evaluations.
The basic strategy is as follows:
- Find out to what (IsEval? ) a GrExpr is evaluated (in attr isEval).
- Bind this info to introduced names (in attr isEvalMp).
- Find out whether a GrExpr will be evaluated later on (in attr willUseFor).
- This is all combined when computing a replacement GrExpr, because closures can only be replaced if it is known that they will be evaluated, and evaluations can only be replaced if we know that they have been computed earlier. Hence the need for past (isEvalMp) and future (willUseFor) info.
- The transformation also computes new IsEval info, to be bound and propagated.
  A tricky issue is the preservation of HPT analysis node/pointer distinction. This is accomplished by:
- Replacement of eval by unit must refer to the node result of the pointer passed to eval.
- Replacement of apply must refer to the original pointer, not an evaluated node.
  For the bytecode interpreter the distinction is useless, even a disadvantage because referring to an original pointer means using an indirection node when the pointer is already evaluated. In that case the node result better be used; this different behavior is made dependent on the target for which code is generated.

*Example 1*

eval x ; \y ->
...
eval x

is replaced by

eval x ; \y ->
...
unit y

*Example 2*

store (#F f x) ; \y ->
...
eval y

is replaced by

call f x ; \y ->
...
unit y

*Example 3*

store (#A f x) ; \y ->
...
eval y
...
eval f

is replaced by

eval f ; \f'
apply f' x ; \y ->
...
unit y
...
unit f'

Note: when HPT analysis is done, in apply the name f is used instead of f'.

(only when optimizing flag is on) AliasElim (again)
(only when compiling to bytecode, and optimizing flag is on) Inline:
Replace references to global values with their actual code. Use of the following are inlined: one-time used functions and values, if not exported; wrappers for primitives (to allow their inline replacement with operators); wrappers for constructors; small enough functions (not yet done).
Requires FlattenSeq to be the next transformation.
(only when compiling to bytecode, and optimizing flag is on) FlattenSeq, AliasElim, EvalElim, AliasElim (again)
(only when compiling to bytecode, and optimizing flag is on) ConstPropagation:
Eliminate name aliases, to avoid unnecessary variable introductions, hence runtime loads. Propagate constants.
(only when optimizing flag is on) UnusedNameElim:
Creation of values that are not needed further downstream the code are eliminated.

2.2 Full program transformations

The following transformations are performed on the full program, when compiling to optimized code:

DropUnreachableBindings:
Drop all functions not reachable from main, either through direct calls, or through deferred (F) or partially applied (P) or apply (A) calls.
CleanupPass:
Clean up the Grin program in two ways: instead of P/0 tags, use F tags; do not delay constructorfunctions: instead of F/Con, use C/Con;
BuildAppBindings:
Replace generic A/ tags by A/app1, A/app2, A/app3 etc. Also build new functions app1, app2, app3 etc.
GlobalConstants:
Lift storing constants to the global level: replace SEQ (STORE (C/c n1 n2)) p body by body and add GLOBAL p = (C/c n1 n2) when all n1, n2 etc are literals.
Inline:
Replace references to global values with their actual code. Use of the following are inlined: one-time used functions and values, if not exported; wrappers for primitives (to allow their inline replacement with operators); wrappers for constructors; small enough functions (not yet done).
Requires FlattenSeq to be the next transformation.
FlattenSeq:
Replace references to global values with their actual code. Use of the following are inlined: one-time used functions and values, if not exported; wrappers for primitives (to allow their inline replacement with operators); wrappers for constructors; small enough functions (not yet done).
Requires FlattenSeq to be the next transformation.
SetGrinInvariant:
Establish the `Grin Invariant': all variables in every GrValL always denotes a pointer, not an (evaluated) node; the name in Eval is always a pointer.
CheckGrinInvariant:
Check how Grin variables are used: as a pointer, or as a node, and whether that is compatible with the way they are created.
This is not a transformation, just an extra check whether SetGrinInvariant worked properly.
EvalStored:
do not do EVAL on pointers that bind the result of a previous STORE.
Instead, do a CALL if the stored node has an F-tag or an A-tag,
or do a UNIT of the stored node for other tags.
DropUnusedExpr:
If an expression is bound to a variable which is never used, it is removed (if the expression has no side effect). Variable bindings that are never used are replaced by wildcards. Global variables and functions thar are never used are removed. Alternatives with tags that involve functions that do no longer exist are removed.
NumberIdents:
Each HsName in the program is numbered. This is done by replacing them with a HsName with constructor HNmNr. In a HNmNr, also the original name is retained, which can be useful later for prettyprinting.
After numbering a toplevel function binding, the unique number is incremented by 2, to reserve a variable number which can be used for analysing the type of an Exception which may be thrown by the function. The parameters of a function are numbered consecutively after that.
PointsToAnalysis:
Traverse a Grin-program it and collect constraint equations which characterize the abstract values of all variables. Then solve the equations, and return the resulting abstract environment: the HptMap. As an additional Int result, return the number of iterations that it took to solve the equations.
This is not a transformation, but a phase that establishes the HPT table.
InlineEA:
Eliminate Grin App and Eval expressions by inlining equivalent code, based on full-program "PointsTo" analysis.
Requires FlattenSeq to be the next transformation. Inspects the HPT table and updates it for introduced fresh variables.
FlattenSeq (again)
DropDeadBindings:
Drop bindings of which static analysis has revealed that they return AbsBottom. Also, remove corresponding alternatives from Case expressions.
For example, if f returns AbsBottom, remove cases F/f and P/f from scrutinizations. Inspects the HPT table, but does not change it.
EmptyAlts:
If the body of a function contains a case-expression with zero alternatives we know that the function can never be called. Replace the binding of the function with the arity placeholder.
DropUnreachableBindings (again)
LateInline:
Inline functions that are used only once.
(To do: inline more functions, e.g. small ones. But than the body should be cloned, with introduced fresh variables etc).
The inlined function is not completely dropped,
because its arity is still needed in SplitFetch.
So we keep a binding with a trivial body.
Requires FlattenSeq to be the next transformation.
Inspects the HPT table, and returns it unchanged. It does not (yet) update the HPT table because it does not yet clone function bodies.
FlattenSeq (again)
ImpossibleCase:
Remove alternatives that, according to HPT, cannot happen.
The user program may distinguish more cases than necessary. Removal of impossible cases saves time. When only one alternative remains, a subsequent SingleCase transformation will remove the scrutinization alltogether. This transformation is particularly effective after the LateInline transformation, as in a particular context more cases might be impossible. In that situation, also alternatives introduced by InlineEA might be removed in a particular context.
Inspects the HPT table, but does not change it.
SingleCase:
If a Case-expression has only a single alternative, replace it by the body of that alternative.
Requires FlattenSeq to be the next transformation.
FlattenSeq (again)
DropUnusedExpr (again)
MergeCase:
Merge two adjacent Case-expressions into one.
The `identity' alternatives of the first are replaced by corresponding alternatives from the second.
The `calling' alternatives of the first are kept, but now flagged as `reentrant' alternatives.
LowerGrin:
Vectorisation: In a lambda pattern n, if HPT says that n refers to a node, replace it by (t x y). Also, in Case expressions, scrutinize on tags rather than nodes.
Inspects the HPT table and updates it for introduced fresh variables.
CopyPropagation (again)
DropUnusedExpr (again)
SplitFetch:
The basic idea is that
```
   fetchnode n; \(x y z) ->
```
is replaced by
```
   fetchfield n 0; \x ->
   fetchfield n 1; \y ->
   fetchfield n 2; \z ->
```
This is done if the tag is statically known, because either x is a constant tag, or HPT analysis reveals that the list of possible tags for n is singleton.
Otherwise, all but the first fetchfield operations are 'floated' to the alternative of a case expression where the tag is known. If such a case expression does not follow, the transformation fails.
Inspects the HPT table and updates it.
DropUnusedExpr (again)
CopyPropagation (again)
ToSilly:
Transforms a Grin program to a Silly program.

2.3 Obsolete transformations

The following transformations seem to be obsolete:

AliasRename
ForceEval
NormForHPT
MergeInstance

3 Silly

3.1 Full program transformations

The following transformations are performed on the Silly program:

Shortcut
EmbedVars
Shortcut (again)
GroupAllocs
PrettyC or ToLLVM

4 EH

Simplified (essential) Haskell.

4.1 Type inference

More entries appear here everytime a module undergoes major changes, and documentation is added as part of such an overhaul.

InferIncrFtv: For generalization the free type variables (tvar) of the global environment are required. Presence of a tvar in this set means no generalization can take place over that tvar. Straightforward computation -compute this set for every def- does not scale up. Here the global ftv is computed separately and incrementally.
Although this file is separated, it should be considered part of EH/Infer, and care should be taken that modifications to the update of environments (valGam, tyGam, ...) are accompanied by changes in the corresponding free var admin here.
FIEnv: Setup various bits and pieces of contextual info needed by fitsIn and other functions: environments (gamma's), options, location info (for error messages), etc.

4.2 Kind inference

5 Ty

Type structure.

5.1 Type

Ftv: Compute free type variables of a type.

5.2 Fitting (aka unification)

5.3 Transformations

Subst: Apply a mapping of type variables to types (or other elements of a type) to a type, as a substitution, replacing found bindings for type variables. On the fly a check is done for circularities in the type variable bindings; this acts as a replacement for the occur check usually done during unification. The check is returned as a map of type variables for which a circularity did occur, to be used for generating error messages elsewhere.
Substitution over a meta level higher is the same as over the current level, except for a shift in the level: - decrement the level of the VarMp used to represent the substitution, lkup - increment the level of
Canonic: Compute canonic form of type so e.g. syntactic equality can be used. This is necessary for:
- Context reduction, i.e. Eq and Ord instances can be used on Ty to compare.
- Foreign function interface (FFI). In both cases the ground form of a type is required, type synonyms expanded, and in the case of newtype also the type level wrapper removed.
  Canonicalization is done at
- rows, where fields may be in arbitrary order.
- types where type synonym expansion may occur, because 2 comparands may be differently partially expanded.
- (FFI only) types which are newtypes because at the value level the type level wrappers (and corresponding constructors) are erased.
- predicates, translated to their witness equivalent, i.e. dictionaries for class predicates; others (like lack predicate for extensible records are ignored). This is only done when types are propagated to Core.
  Tricky implementation point: After type synonym expansion, the replacement probably is structurally different and must be canonicalized as well! Hence the Maybe return signalling a replacement requiring recursive canonicalization of inner components, type level beta reduction and canonicalization alternately done.
  A VarMp (substitution) with additional changes in the type is threaded. Currently (20090821) only empty implicits Impls_Tail are replaced by Impls_Nil, and removed in the type itself.
BetaReduce: Beta reduce types
- Type lambdas Ty_Lam are applied to their arguments.
- Type constants Ty_Con are expanded to their definition.
- (Polarity inferencing only) Special cases are treated: negation of negation, in particular.
  All is paremeterized with lookup for type constants. The reduction is limited by the expansion cutoff limit indicated by option ehcOptTyBetaRedCutOffAt.

6 Foreign

Representation of FFI entities

6.1 Foreign

Parser: Parse a foreign entity. Parsing is parameterized with:
- The calling convention (encoded by FFIWay), determines which parser is used as the syntax depends on the calling convention.
- A name, to be used when a name is absent. This feature is to be used for a first parse only, after that the name should be explicitly specified. This is to cater for ccall calling convention which allows (e.g.) an include file only (taken from library module Foreign.Marshall.Utils):
```
foreign import ccall unsafe "string.h" memcpy  :: Ptr a -> Ptr a -> CSize -> IO (Ptr a)
```

7 JVMClass

JVM class structure

7.1 Class

Representation of JVM class files. For reference see:

This AST and semantics are under construction.

8 CLR backend

The CLR backend is a highly experimental backend for the EHC developed during the Advanced Compiler Construction seminar in early 2009.

8.1 Overview

8.1.1 Common Language Runtime

The Common Language Runtime (CLR) is a runtime system, developed by Microsoft as .NET, that runs managed code. It exposes facilities such as a common type system, memory management and just in time compilation. Currently the three most promiment implementations are:

.NET on the Windows desktop
Mono under Linux/OS~X machines
Silverlight for running in the browser on Windows and OS~X

The code generated by the EHC backend has been tested on both .NET for Windows and Mono (OS~X, Linux).

8.1.2 EHC backend

The experimental backend adds a new target to generate assembly files for the CLR. Using the flag -tclr, the compiler can be directed to generate .il files that contain Common Intermediate Langauge (aka MSIL) assembly code.

These .il files can be assembled into .exe files using ilasm.exe under Windows (available in %WINDOWS%\Microsoft.NET\Framework\v2.0.50727\) and ilasm2 under Linux/OSX (available through Mono).

Here is a running scenario:

$ cat > Test.hs
const x y = x
main = const 8 15
^C
$ EHC/install/8/bin/ehc -tclr Test.hs
$ ilasm2 Test.il
$ mono Test.exe
Int 8

Note: This chapter describes some technical aspects of the implementation, but it doesn't describe the underlying ideas.

Ideally, a new separate document will be written detailing the underlining concepts of the CLR backend. However, such a document doesn't yet exist, for now there are just the slides and a video from the authors from the final presentation of the Advanced Compiler Construction seminar.

8.2 Architecture

Currently, the CLR backend only works in variant 8 of the EHC. Work is being done to get variant 100 to comipile.

8.2.1 language-cil

The CLR backend makes use of an external library called language-cil. This library exposes an AST, build functions and pretty printers for the Common Intermediate Language (CIL).

This library will need to be installed before compiling the EHC.

At some point in the future language-cil will be uploaded to Hackage, however currently it lives just in source control: https://svn.cs.uu.nl:12443/repos/language-cil/tags/0.1.0/

8.2.2 /src/ehc/Cil/Common.chs

8.2.3 /src/ehc/Cil/TyTag.chs

8.2.4 /src/ehc/GrinCode/ToCil.chs

8.3 Tests

In the directory /test/clr are some CLR test cases, some of which don't compile anymore, see open issues.

8.4 Open issues

Some open bugs which haven't been resolved yet:

/tests/5-tailcalls Fails due to the fact that one tail call to many is generated.
/tests/8-fibs Fails. App TyTag isn't implemented yet (Con, Fun and PApp are).

8.5 Todo

Document conceptual ideas behind architectural choices.
Remove ReferenceObject indirection.
Better support for primitive types, GrPatLam.EnumAnnot is hardcoded to booleans.
Become more stack-oriented (move to Silly?).
Make use of stack allocated objects (Value types).
Use more unboxed types, adding two integers shouldn't have to create 6 heap objects.
Use generic types instead of using container types for primitives.