llvm's role in addx

4.22: addm/llvm's role in addx:
. why can't addm just run llvm code?
isn't elegance a dumb place to put an asm lang?
# c-friendly:
the whole point of addm is to
minimize dependencies;
many systems have no llvm system
but do have a c compiler .
# simplicity = involvement:
. while llvm is all about efficiency,
addx is about making computers accessible .
. just as there can be
cpu's designed for a language,
addm's purpose as a virtual machine
is to match the architecture of adda .
. llvm does fit in as a module:
it would be a tremendous achievement
-- on par with Apple's llvm for obj'c --
to have a way for directly translating
from addm to llvm
rather than the c link used now:
adda -> c -> llvm .

LLVM concurrency representations

Mac OS X 10.6 (and later):

. The OpenCL GPGPU implementation is built on
Clang and LLVM compiler technology.
This requires parsing an extended dialect of C at runtime
and JIT compiling it to run on the
CPU, GPU, or both at the same time.
OpenCL (Open Computing Language)
is a framework for writing programs
that execute across heterogeneous platforms
consisting of CPUs, GPUs, and other processors.
OpenCL includes a language (based on C99)
for writing kernels (functions that execute on OpenCL devices),
plus APIs that are used to define and then control the platforms.

Open for Improvement:

. With features like OpenCL and Grand Central Dispatch,
Snow Leopard will be better equipped
to manage parallelism across processors
and push optimized code to the GPU's cores,
as described in WWDC 2008: New in Mac OS X Snow Leopard.
However, in order for the OS to
efficiently schedule parallel tasks,
the code needs to be explicitly optimized
for for parallelism by the compiler.
. LLVM will be a key tool in prepping code for
high performance scheduling.

LLVM-CHiMPS (pdf)
LLVM for the CHiMPS 
(Compiling hll to Massively Pipelined System)
National Center for Supercomputing Applications/
Reconfigurable Systems Summer Institute July 8, 2008/
Compilation Environment for FPGAs:

. Using LLVM Compiler Infrastructure and
CHiMPS Computational Model
. A computational model and architecture for
FPGA computing by Xilinx, Inc.
- Standard software development model (ANSI C)
Trade performance for convenience
- Virtualized hardware architecture
CHiMPS Target Language (CTL) instructions
- Cycle accurate simulator
- Runs on BEE2
Implementation of high level representations:

# Limitations in optimization
- CTL code is generated at compile time
No optimization by LLVM for a source code in which no
such expressions can be optimized at compile time
- LLVM does not have a chance to dynamically optimize
the source code at run time
- LLVM is not almighty
Floating point math is still difficult to LLVM

Cray Opteron Compiler: Brief History of Time (pdf)

Cray has a long tradition of high performance compilers
Vectorization
Parallelization
Code transformation
...
Began internal investigation leveraging LLVM
Decided to move forward with Cray X86 compiler
First release December 2008

Fully optimized and integrated into the compiler
No preprocessor involved
Target the network appropriately:
.  GASNet with Portals . DMAPP with Gemini & Aries .
Why a Cray X86 Compiler?
Standard conforming languages and programming models
Fortran 2003
UPC & CoArray Fortran
. Ability and motivation to provide
high-quality support for
custom Cray network hardware
. Cray technology focused on scientific applications
Takes advantage of Cray’s extensive knowledge of
automatic vectorization and
automatic shared memory parallelization
Supplements, rather than replaces, the available compiler choices

. cray has added parallelization and fortran support .
. ported to cray x2 .
. generating code for upc and caf (pgas langs) .
. supports openmp 2.0 std and nesting .

. Cray compiler supports a full and growing set of
directives and pragmas:
!dir$ concurrent
!dir$ ivdep
!dir$ interchange
!dir$ unroll
!dir$ loop_info [max_trips] [cache_na] ... Many more
!dir$ blockable
man directives
man loop_info
weaknesses:
Tuned Performance
Vectorization
Non-temporal caching
Blocking
Many end-cases
Scheduling, Spilling
No C++, Very young X86 compiler
future:
optimized PGAS -- requires Gemini network for speed
Improved Vectorization
Automatic Parallelization:
. Modernized version of Cray X1 streaming capability
. Interacts with OMP directives
[OpenMP -- Multi-Processing]

D language

7.16: news.adda/lang"D:

. reasons to rewrite C to D?

. C is missing module support?
-- that feature helps figure out
where a function is defined;
but, cscope does that too .

. D was designed to remove
most of the flaws from C and C++,
while keeping the same syntax,
and even binary compatibility with C...
and almost binary compatibility with C++.
[. actually,
C syntax is a flaw too,
having decl's only a compiler could love .]

. D is also a mix of low-level
(x86 assembly is part of the language)
and higher-level characteristics
(optional gc, modules,
a fix of C++ templates, etc.).
. implementations include
front ends for LLVM and gcc .
. tango is the community replacement for
digitalmars`Phobos system library .
[7.27:
. unless there's something your lang needs
that simply can't be done in C,
the most simple and portable way
to enjoy working in your own lang,
is to just translate your lang to C .
. that route is esp'ly handy for
platforms like Apple's,
where you really need to be
using their tools .
. having translated to C,
I'm already half-way toward
translating for obj'c and cocoa .]

llvm and .NET or lisp

3.20: addx/llvm and .NET or lisp:

. how did llvm fit in with .net?
the .net was an improvement over bytecode;
it had a binary format of high-level code
-- call it wordcode --
and any language could compile to that wordcode .
. there's security in the wordcode,
since it's easy to verify it's not malware,
then a platform-specific runtime can
translate wordcode into an exec.file .
. llvm presents itself as the universal asm.code
(source code of a machine instruction set)
so one quick way to roll a wordcode compiler
is to compile wordcode to asm.code .
. then the llvm for that platform
will do all the heavy lifting of
jit-compiling and dynamic morphing
that keeps the asm.code mirrored in
the most efficient version of native code
for the current circumstances .
. there need be no practical difference between
word.code and the etrees of lisp
and perhaps that's why Stallman would
downplay .net as a Microsoft false freebee .
. what we really need from .net
is something more lisp-like
where the only constant to the std
is that etrees describe the conventions
of the current package .
. what we really need from lisp
is the same binary std for word.code
that .net calls assemblies .
. at the moment lisp's std is text-based
not binary -- xml is the same thing:
people should be communicating with that
only as a last resort,
when no binary convention has been agreed upon .
3.23:
. Mono from SVN is now able to use LLVM as a backend .

3.22: addx/security/review:
. what was the system that offered better security than
soa's token-based (smart-carded) logged messaging ?
. how did it differ from virtualization ?
. the first wall starts with using source code
rather than binaries:
. a program is an adda binary
that is then compiled to addx code
which is native code but can access only addx
(assured from being compiled by adda),
and then only addx can access actual devices .
. with this separation of power,
the program can tell addx what it needs
and then the user can tell addx
whether those needs sound reasonable .
. an adda binary is an etree (a parse tree)
where half of the compilation is already done:
. after adda text is parsed into etrees,
the etrees are safely translated by adda
to a system lang for compilation into a native binary .
. in essence the adda program has written the program;
if the original author had
programmed in the system lang'
then it could unsafely have
direct access to the machine .
. this is not unlike the .net security strategy;
but, addx is not concerned about supporting
multiple source lang's . [3.31: nevertheless,
adda's etree could be the target of
some other lang's compiler, for piping:
[your lang] -> adda`etree -> [some adda`backend] ]
. both { .net, adda } have a binary format
for sharing code, but .net's assemblies
may be more thoroughly processed than parse trees .
[3.31: and conversely, parse trees are in a
more modifiable, machine-comprehensible state
than .net's assemblies .]
. the ideal situation is to translate adda etrees
directly into llvm code,
but the easiest way to build addx in a portable way
is translating adda etree to the source text
of the language that the target platform prefers;
eg, when on the mac, the target language is
c, obj'c, and the cocoa framework;
while on linux and elsewhere,
it would be c, c++, and the qt framework .

. on the Android OS, the main source of
security is a slow vm
that compounds the speed hit caused by
addx's security not allowing
direct access to anything;
addx is asking every cross-module communication:
"(who are you,
and do you have permissions for that?)
. then if addx is to run dynamically modified code,
it's running a vm within a vm,
and things get even slower!

. the .net idea of security is much faster
than any vm security (even Dalvik)
but perhaps that speed
would come at the cost of space
-- the Android fits within 64mb .
. or,
perhaps because of patents,
any open system that was like .net
would not be easy to defend .
. the primary reason I'm not bothering to check
is that .net's idea is not nearly as simple as mine!
. you can avoid a lot of low-level programming
if you just learn the target's high-level language,
and do a simple lang-to-lang translation .
[3.31:
. actually what .net is essentially doing is
unpacking assemblies into etrees,
checking them the way adda would,
then translating them to
the etrees of some native compiler,
and compiling them dynamically .
. it's that dynamics that gives it the name .net;
that's the basis for dynamically accepting code
from other websites in a safe way .
. it may not need to get low-level,
but translating between etree formats
is definitely more complex than source-to-source .]

c-- (c minus minus.org)

5.1: news.addm/c--/haskell won't be using LLVM:

LHC won't be using LLVM.

In this post I will elaborate on

why some people think

C-- has more promise than LLVM

as a substrate for lazy, functional languages.

Let me start by making one thing clear:

LLVM does have support for garbage collectors.

I am not disputing that.

However, as Henderson has shown,

so does C and every other language.

The question we have to ask is not

"Does this environment support garbage collection?"

but rather

"How efficiently does this environment

support garbage collection?".

To recap,

Henderson's technique involves placing

root pointers

(the set of pointers which can be

followed to find all live data)

on a shadow stack.

Since we manage this stack ourself,

it shouldn't be a problem for the GC to walk it.

In short, each heap allocation incurs

an unnecessary stack allocation

and heap pointers are

never stored in registers for long.

Now what does this mean for

languages like Haskell?

Well, unlike programs written in

more traditional languages,

a Haskell application might very well

do between 10 and 20 million

heap allocations per second.

Writing Haskell programs is more about

producing the correct data stream

than it is about performing the right side-effects

. It's common for functions in Haskell

to manipulate data without execuing

any side-effects. (Think spreadsheets.)

This way of computing obviously requires

a very cheap method of allocation.

Performing 10 million unnecessary

stack allocations per second

would severely hurt performance,

and not having heap pointers in registers

could easily be equally devastating.

So what about LLVM?

Shouldn't the built-in GC support in LLVM

be more efficient than any cheap hack?

Well, it turns out it isn't.

The conflict between garbage collection

and optimizations haven't changed,

and neither have the solution:

disabling or bypassing optimizations.

This in turn means unnecessary stack allocations

and sub-optimal use of registers.

That LLVM'ers haven't solved the problem of

zero-overhead garbage collection

isn't too surprising

. Solving this while staying agnostic of the data model

is an open question in computer science.

It is here C-- differs from LLVM

. C-- is a research project that aims at solving

difficult problems such as supporting efficient GCs

and cheap concurrency.

LLVM, on the other hand, is an engineering project.

In conclusion:

garbage collection in LLVM incurs

unacceptable overhead,

and while C-- and LLVM do have some overlap,

the problems they're trying to solve are quite different.

Posted by David Himmelstrup at 11:52 AM

5.2: co.addm/stackoverflow.com/llvm vs c--:

addn/net.stackoverflow.com/questions/

llvm vs c-- ; how can llvm fundamentally

not be better for haskell than c-- ?

ask a queston: (tags: LLVM llvmclang haskell c--)

I've been excited about llvm being

low enough to model any system

and saw it as promising

that Apple was adopting it,

but then again

they don't specifically support Haskell,

and some think that Haskell

would be better off with c--

adding that there's

nothing llvm can do to improve .

> That LLVM'ers haven't solved the problem of

zero-overhead garbage collection

> isn't too surprising .

> Solving this while staying agnostic of the

data model

> is an open question in computer science.

I am refering to

news.addm/c--/haskell won't be using LLVM

5.9: answer accepted:

Well, there is a project at UNSW

to translate GHC Core to LLVM

Remember: it wasn't clear 10 years ago

that LLVM would build up all the

infrastructure C-- wasn't able to

. Unfortunately,

LLVM has the infrastructure for

portable, optimized code,

but not the infrastructure

for nice high level language support,

that C-- ha(s)d.

An interesting project

would be to target LLVM from C-- ..

comment to answer:

. great answer; that was

just the blindspot-undo I was looking for!

. llvm'ers had a similar response

to the lack of concurrency support:

it's an add-on library thing .

. c-- can be ported to llvm,

meaning that llvm's gc simply won't be used .

11.9: web.adda/c--/review:

cminusminus.org/papers.html

C-- is a compiler-target language.

The idea is that a compiler for a high-level language

translates programs into into C--,

leaving the C-- compiler to generate native code.

C--'s major goals are these:

C-- is not "(write-once, run-anywhere) .

It conceals most architecture-specific details,

such as the number of registers, but it exposes some.

In particular, C-- exposes the word size, byte order,

and alignment properties of the target architecture, for two reasons.

First, to hide these details would require

introducing a great deal of complexity, inefficiency, or both

-- especially when the front-end compiler

needs to control the representation of its high-level data types.

Second, these details are easy to handle in a front-end compiler.

Indeed, a compiler may benefit, because

it can do address arithmetic using integers

instead of symbolic constants such as FloatSize and IntSize.

web.adda/what do the c-- folks think of llvm?

summary:

. why isn't the llvm project working for c-- users?

llvm makes the assumption that there exists a generic assembler,

and c--, by assuming otherwise,

is not about portability:

the current version targets only the intel'86 architecture .

lhc-compiler.blogspot.com/2009/01/case-against-llvm

I do not understand the assertion that LLVM is uncooperative.

The direction LLVM takes is driven entirely by contributors.

I suggest you embrace this

and implement the necessary GC support in LLVM.

The devs would likely be happy to help out with any problems;

the team is *very* helpful.

Furthermore,

that support would open the door to implementing

other similar functional languages in LLVM,

rather making more isolated code islands.

In the long run, LHC will win *big*

by having that same code used by others

(and tested, and expanded.)

There are many things for which it is reasonable to have

NIH (Not Invented Here syndrome).

In 2009, a fast code generator is not one of them.

David Himmelstrup said...

It's unsolved in the academic sense of the word.

Solving it requires research and not engineering.

If I knew how to solve it, I definitely would add it to LLVM.

It's only unsolved in the general case.

I doubt, however, that LLVM is interested in my specific data model

(which is in a state of flux, even).

lhc-compiler.blogspot.com/2009/01/llvm-is-great

what I want to do

can't yet be done by any general-purpose compiler.

C-- status report: yes, someone is (barely) out here

Chris Lattner

Sun, 17 Dec 2006 12:45:42 -0800

LLVM is written in C++, but, like C--, it provides first-class support for

intermediate representation written as a text file (described here:

http://llvm.org/docs/LangRef.html), which allows you to write your

compiler in the language that makes the most sense for you.

In addition to the feature set of C--, LLVM provides several useful pieces

of infrastructure: a C/C++/ObjC front-end based on GCC 4, JIT support,

aggressive scalar, vector (SIMD), data layout, and interprocedural

optimizations, support for X86/X86-64/PPC32/PPC64/Sparc/IA-64/Alpha and

others, far better codegen than C--, etc. Further, LLVM has a vibrant

community, active development, large organizations using and contributing

to it (e.g. Apple), and it is an 'industrial strength' tool, so you don't

spend the majority of your time fighting or working around our bugs :).

Like C--, LLVM doesn't provide with a runtime (beyond libc :) ), which can

be a good thing or a bad thing depending on your language (forcing you to

use a specific runtime is bad IMHO). I would like to see someone develop

a runtime to support common functional languages out of the box better

(which language designers could optionally use), but no-one has done so

yet.

OTOH, C-- does have some features that

LLVM does not yet have first class support for.

LLVM does not currently support for generating efficient code

that detects integer arithmetic overflow, doesn't expose the

rounding mode of the machine for FP computation, and does not yet support

multiple return values, for example.

While it is missing some minor features, one of the most important

features of LLVM is that it is relatively easy to extend and modify. For

example, right now LLVM's integer type system consists of signed and

unsigned integers of 1/8/16/32 and 64-bits. Soon, signedness will be

eliminated (giving us the equivalent of C--'s bits8/bits16/bits32/bits64

integer types) and after that, we plan to generalize the integer types to

allow any width (e.g. bits11). This is intended to provide better support

for people using LLVM for hardware synthesis, but is also useful for

precisely constrainted types like those in Ada (i.e. it communicates value

ranges to the optimizer better).

> I think the three new things I'd like to see out of C-- are (in rough

> order of priority):

> 1) x86-64 support

> 2) the ability to move/copy a stack frame from one stack to another, and

> 3) Some form of inline assembler without having to go to C (necessary for

> writting threading primitives in C--)

LLVM provides #1 and #3 'out of the box'. #2 requires runtime

interaction, which would be developed as part of the runtime aspect.

For me, one disappointment of the LLVM project so far is that we have not

been very successful engaging the functional language community. We have

people that use LLVM as "just another C/C++/Objc compiler", we have people

that reuse the extant front-ends and optimizer to target their crazy new

architectures, and we have mostly-imperative language people (e.g. python)

using LLVM as an optimizer and code generator. If we had a few

knowledgable people who wanted to see support for functional languages

excel, I believe LLVM could become the premier host for the functional

community.

If you are considering developing aggressive new languages, I strongly

recommend you check out LLVM. The llvmdev mailing list

(http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev)

is a great place to ask questions.

2006

> For me, one disappointment of the LLVM project so far

is that we have not been very successful engaging the

functional language community.

If you want to engage functional programmers,

you're not publishing in the right places.

PLDI gave up on functional programming long ago,

(Programming Language Design and Implementation)

and therefore

many functional programmers

no longer pay much attention to PLDI.

. the largest stumbling blocks for the industry adoption of

languages like Haskell and c--

is the fact that it still markets itself as

some mathematics/computer science professor's little experimental project.

I feel C-- still suffers a bit from "professor's pet project" syndrome a bit .

> - GCC: Still quite complicated to work with, still requires you to write

> your compiler in C. Implementing a decent type system is going to be

> interesting enough in Ocaml or Haskell, I'll pass on doing that in C.

> Which means a hybrid compiler, with a lot more complexity. Also,

> functional languages are definately still second class citizens in GCC

> world- things like tail call optimization are still not where they need to

> be. Which means implementing an optimization layer above GCC to deal with

> tail calls. Plus you still have all the run time library issues you need

> to deal with- you still need to write a GC, exception handlers, threading,

> etc. On the plus side, you do get a lot of fancy optimizations- SSE use,

> etc.

Where functional programming really shines, I think,

is programming in the large- word processors and CAD/CAM systems etc.

It's when you start dealing with things like maintainance

and large scale reuse and multithreading that

> functional programming really spreads it's wings and flies.

And, unlike scripting/web programming, performance really does matter.

>

> - Use C as a back-end. You're writing your own runtime again, tail

> recursion is poorly supported again, and a lot of function programming

> constructs don't map well to C.

> - Use C--. You still have to implement your runtime, but you're basically

> going to have to do that anyways. You get decent optimization, you get to

> write your compiler in the language you want to, and functional languages

> are first class languages.

>

> Of these options, I think C-- (assuming it's not a dead project) is the

> best of the lot. Even if it needs some work (an x86-64 back end, the

> ability to move a stack frame from one stack to another), it'll be no more

> work than any other option. My second choice would be GCC as a back end,

> I think. But the point here is that the fundamental niche C-- fills is

> still usefull and needed.

>

LLVM is very C-ish,

and makes it rather awkward to have

procedure environments and goto's out of procedures

Oct 2008 01:45:11 -0700

| Most of our users have reported that it is very easy to adapt a legacy

| compiler to generate C-- code, but nobody has been willing to attempt

| to adapt a legacy run-time system to work with the C-- run-time interface.

I don't know whether this'll be any use to anyone except us,

but we're using C-- like crazy inside GHC (the Glasgow Haskell Compiler).

But not as an arms-length language.

Instead,

inside GHC's compilation pipeline we use C-- as an internal data type;

and after this summer's work by John Dias,

we now have quite a respectable

story on transforming,

and framework for optimizing,

this C-- code.

Since some of the runtime system is written in C--,

we also have a route for parsing C-- and compiling it down the same pipeline.

All that said,

this is a *GHC specific* variant of C--.

It does not support the full generality of C--'s runtime interface

(it is specific to GHC's RTS), nor is it intended as a full C-- implementation.

In its present state it's not usable as a standalone C-- compiler.

Still, it is a live, actively-developed implementation

of something close to C--, and so might be of interest to some.

http://lists.cs.uiuc.edu/pipermail/llvmdev/2009-January/019461.html

The OCaml Journal has published around 40 articles now. The most popular and

third most popular articles are both about LLVM. So I don't think it is

correct to say that "functional language people don't like LLVM". Indeed, I

thought I was a kook for trying to write a compiler for a functional language

using LLVM until I mentioned it to the OCaml community and half a dozen

people stepped forward with their own alternatives. :-)

-- Dr Jon Harrop, Flying Frog Consultancy Ltd.

to llvm or not

6.6: summary
. let clang translate hll to llvm,
and let adda take the much smaller step of
transforming adda`hll to clang`hll -- obj'c (which includes plain c) .

5.1: web.addm/what's new with llvm?

The llvm-py is a Python package, consisting of 6 modules,

that wrap over enough LLVM APIs to allow the implementation of

your own compiler/VM backend in pure Python .

where is llvm in concurrency? (vid)

. you can extend the llvm

just as you can reach any libraries you want from c .

. this is how Apple`c gives access to concurrency .

5.1: addm/python concurrency is alive despite gil:

. some at code.google are doing

something like pypy,

but the emphasis is llvm

not python coded in itself:

. they intend to remove the GIL

and fix the state of multithreading in Python

. We believe this is possible through

the implementation of a more sophisticated

GC system, something like IBM's Recycler

(Bacon et al, 2001).

. here is their comment on

an llvm binding for python:

llvm-py has such wrapper types,

but using Python-defined types

in the core interpreter

is very difficult,

so we'll write our own

. These won't be full wrappers

(leave that to llvm-py)

. Just what's convenient and useful for debugging.

python has concurrency via lib's too:

The switch to LLVM

itself isn't solving the

concurrency problem

. That's being solved separately,

by getting rid of the Global Interpreter Lock.

I like the GIL; it makes my life a lot easier

not having to think about

tricky synchronization issues.

I use threads mainly to deal with

blocking I/O,

not to take advantage of multicore processors

(for that, I would use the multiprocessing module

to spawn separate processes).

5.1 web.addm/llvm vs c--/news of libJIT starts critique of llvm

I can recommend libJIT for its simplicity

and performance (LLVM is overkill):

. just a couple of things

LLVM did not easily support for us:

in .NET and Microsoft CIL

(Common Intermediate Language ECMA-335):

* the whole spectrum of ECMA 335 for

CLR types and operations

* async exception handling

* precise stack marking

* multiple custom call conventions

* fast Just-In-Time compilation

All these features are supported in libJIT.

Also libJIT has been already used

and well tested in real life

in DotGNU Portable.NET Just-In-Time compiler, ILDJIT,

and, moreover, in HornetsEye

where libJIT is integrated with Ruby

to accelerate video and image digital signal processing.

See also

other information about why LLVM is overkill,

from people who have done a lot of research on

JIT compilation:

http://lists.ximian.com/pipermail/mono-devel-list/2009-April/031640.html

http://lists.gnu.org/archive/html/dotgnu-libjit/2004-05/index.html

(Rhys Weatherley (libJIT) vs Chris Lattner (LLVM))

Try to Google for libJIT.

Look for very detailed technical information here:

http://www.gnu.org/software/dotgnu/libjit-doc/libjit_1.html

http://en.wikipedia.org/wiki/LibJIT

http://code.google.com/p/libjit-linear-scan-register-allocator/

libJIT is both much easier and much faster than LLVM.