[LLVMdev] Fibonacci example in OCaml

[Gordon Henriksen]

On 2007-11-26, at 21:12, Jon Harrop wrote:

> Provide a type enumerating the valid terminators and restrict the  
> last instruction in a block to be a terminator. Something like this:
>
>  type terminator = [ `ret of llvalue | `br of llvalue ]
>  type instruction =
>      [ terminator
>      | `add of llvalue * llvalue
>      | `sub of llvalue * llvalue ]
>  type block = instruction list * terminator
>
> If you want to avoid having a data structure representing the input  
> to LLVM then you can probably achieve the same result using  
> combinators, e.g. by having the building functions for terminators  
> change an [`incomplete] block into a [`complete] block. However,  
> that might make the bindings harder to use.

Intermediate states are important, though they might be invalid. This  
is inherited from the underlying object model. I don't think validity  
is a concept that can effectively be grafted in through the type  
system of a binding.

> Use phantom types to track the type of each llvalue:
>
>  type 'a llvalue

This does not cover the full generality of the IR. The first argument  
to a call instruction need not be a Function. Rather, the type of the  
value must be pointer to function.

Still, those phantom types may be a solution for binding the Value  
hierarchy without introducing gratuitous static casts. (The argument  
to set_visibility must be a GlobalValue, for instance.) Can you  
represent multiple-level inheritance? Value -> GlobalValue ->  
GlobalVariable, say.

> I would use polymorphic variants more, particularly for enums and  
> types that are only used once (e.g. "linkage" and "visibility"). So  
> types would be `i32 rather than i32_type

Types are not enums, they're first-class objects.

> and int_predicate and real_predicate would become overlapping sum  
> types, e.g. `ugt is valid for both.

These variant types were set up to have a 1:1 correspondence with the C 
++ enums, and I'd prefer to keep that. There's also no overlap for  
integer and FP predicates (unsigned greater than is not unordered  
greater than).

> I'd also rather see structuring than identifier bloat, e.g.:
>
> module Linkage = struct
>  type linkage =
>      [ `External
>      | ...
>      | `Ghost ]
>
>  external linkage : llvalue -> linkage = "llvm_linkage"
> end

This is a fair idea for grouping enums.

>> It should be possible for LLVM to perform intra- or interprocedural  
>> escape analysis and lower heap allocations to stack allocations,  
>> but I don't believe this is implemented. Garbage collection would  
>> also complicate it, since LLVM would need to recognize GC allocator  
>> functions as such. This would be an excellent project if you are  
>> interested in contributing to LLVM itself.
>
> Perhaps such optimizations would be better done at a higher-level,  
> above the level of the GC? So that would be ideal for a higher-level  
> VM on top of LLVM.

Escape analysis is perfectly practical on the LLVM representation.

Reorganizing data structures is probably best done by the language  
front end. A functional language is the ideal host for such  
experiments. The closest LLVM does is SROA.

— Gordon