grin

GRIN is a compiler back-end for lazy and strict functional languages with whole program optimization support.

Stars
1K
Committers
17
View Code on GitHub Visit Website
Ecosystems: LLVM, Haskell

GRIN

The name GRIN is short for Graph Reduction Intermediate Notation, and it is an intermediate language for graph reduction. GRIN is the optimizer and code generator component of the GRIN Compiler project which includes language frontends for Haskell, Idris and Agda. To get the big picture of the project check the project website. For an overview of the optimizer read The GRIN Project paper. To grasp the details take your time and read Urban Boquist's PhD thesis on Code Optimisation Techniques for Lazy Functional Languages .

Presentations

  • We presented the core ideas of GRIN at Haskell Exchange 2018. slides video
  • The Next-gen Haskell Compilation Techniques (2021) presentation gives a high-level overview of the project motivation. slides video

Read our paper A modern look at GRIN, an optimizing functional language back end (2019) to get an overview of GRIN related projects and other whole program compilers i.e. Boquist GRIN, UHC, JHC, LHC, HRC, MLton

Also check the GRIN transformation example from Boquist PhD and an example from our implementation.

Support

The project is supported by these awesome backers. Special thanks to our gold sponsors:

Sam Griffin

If you'd like to join them, please consider become a backer or sponsor on Patreon.

GRIN IR

Showcase

Setup

Installing LLVM

Homebrew

Example using Homebrew on macOS:

$ brew install llvm-hs/llvm/llvm-7

Debian/Ubuntu

For Debian/Ubuntu based Linux distributions, the LLVM.org website provides binary distribution packages. Check apt.llvm.org for instructions for adding the correct package database for your OS version, and then:

$ apt-get install llvm-7-dev

Nix

To get a nix shell with all the required dependencies do the following in the top level folder.

nix-shell

To run the example do the following from the top level folder.

(cd grin; cabal run grin -- grin/opt-stages-high-level/stage-00.grin)

To run a local Hoogle server with Haskell documentation do the following.

hoogle server --port 8087 1>/dev/null 2>/dev/null&

Build GRIN

stack setup
stack build

Usage

stack exec -- grin grin/grin/opt-stages-high-level/stage-00.grin

How to Contribute

See: Issues / Tasks for new contributors Keep it simple: We follow the fundamentals laid down in HaskellerZ - Feb 2018 - Getting things done in Haskell

Example Front-End

Read about how to generate GRIN code from a frontend language.

Also check the corresponding source code.

i.e.

Simplifying Transformations

Transformation Schema
vectorisation source code: Vectorisation2.hs
case simplification source code: CaseSimplification.hs
split fetch operation source code: SplitFetch.hs
right hoist fetch operation source code: RightHoistFetch2.hs
register introduction source code: RegisterIntroduction.hs

Optimising Transformations

Transformation Schema
evaluated case elimination source code: EvaluatedCaseElimination.hs test: EvaluatedCaseEliminationSpec.hs
trivial case elimination source code: TrivialCaseElimination.hs test: TrivialCaseEliminationSpec.hs
sparse case optimisation source code: SparseCaseOptimisation.hs test: SparseCaseOptimisationSpec.hs
update elimination source code: UpdateElimination.hs test: UpdateEliminationSpec.hs
copy propagation source code: CopyPropagation.hs test: CopyPropagationSpec.hs
late inlining source code: Inlining.hs test: InliningSpec.hs
generalised unboxing source code: GeneralizedUnboxing.hs test: GeneralizedUnboxingSpec.hs
arity raising source code: ArityRaising.hs test: ArityRaisingSpec.hs
case copy propagation source code: CaseCopyPropagation.hs test: CaseCopyPropagationSpec.hs
case hoisting source code: CaseHoisting.hs test: CaseHoistingSpec.hs
whnf update elimination source code: TODO test: TODO
common sub-expression elimination source code: CSE.hs test: CSESpec.hs
constant propagation source code: ConstantPropagation.hs test: ConstantPropagationSpec.hs
dead function elimination source code: SimpleDeadFunctionElimination.hs test: SimpleDeadFunctionEliminationSpec.hs
dead variable elimination source code: SimpleDeadVariableElimination.hs test: SimpleDeadVariableEliminationSpec.hs
dead parameter elimination source code: SimpleDeadParameterElimination.hs test: SimpleDeadParameterEliminationSpec.hs
Badges
Extracted from project README's
Build Status Coverage Status Gitter chat
Related Projects
awesome-graal

A curated list of awesome resources for Graal, GraalVM, Truffle and related topics

09 Aug 2017 355
accelerate

Embedded language for high-performance array computations

08 Apr 2011 896
code-clone-detection-llvm-devmtg15-poster

Code Clone Detection in Clang Static Analyzer poster for LLVM Developers' Meeting 2015.

20 Oct 2015 8
llvm-ir

LLVM IR in natural Rust data structures

11 Jul 2019 539
hwtHls

LLVM based HLS library for HWToolkit (hardware devel. toolkit)

22 Dec 2016 24
llvmbpf

Userspace eBPF VM with llvm JIT/AOT compiler

09 Aug 2024 48
LLVM-Middle-End-Optimizations

Machine independent passes to optimise LLVM intermediate representation.

04 Apr 2024 5
awesome-llvm

A curated list of awesome LLVM (including Clang, etc) related resources.

14 Jan 2015 479
haybale-pitchfork

Verifying constant-time code with symbolic execution

06 Aug 2019 40
Dependency

24 Jan 2019 20
llvm-tutor

A collection of out-of-tree LLVM passes for teaching and learning

25 Mar 2019 2,924
setup-cpp

Install all the tools required for building and testing C++/C projects.

14 Sep 2021 190
codegen

Experimental wrapper over LLVM for generating and compiling code at run-time.

08 May 2019 381
llvm-tutorial-in-rust-using-inkwell

An implementation of Kaleidoscope, the LLVM tutorial model language, written in Rust using Inkwell.

28 Apr 2024 6
gocaml

Statically typed functional programming language implementation with Go and LLVM

25 Jan 2017 747