From an Interpreter to a Compiler

My name is Justin Hendrick and I'm an intern working on ParaSail for the summer. My first task is code generation.

Up until now, ParaSail has been interpreted. We’re proud to announce that we’ve begun building the code generation phase, written in ParaSail, that generates LLVM Intermediate Representation code. For information about LLVM see llvm.org and the reference manual.

So far, we can successfully compile simple functions that branch and do arithmetic on Univ_Integers and Univ_Reals.

For example, this ParaSail max function:

func Max(A : Univ_Integer; B : Univ_Integer) -> Univ_Integer is
   if A > B then
      return A;
   else
      return B;
   end if; 
end func Max;

Is converted to ParaSail Virtual Machine Intermediate Representation. See this post for more details on the PSVM and the calling convention in use.

 ----- ParaSail Virtual Machine Instructions ---- 
Max: Routine # 720
(A : Univ_Integer<>; B : Univ_Integer<>) -> Max : Univ_Integer<>
Uses_Queuing = FALSE
Local_Area_Length = 17
Start_Callee_Locals = 7
Code_Length = 13
(COPY_WORD_OP, Destination => (Local_Area, 5), Source => (Param_Area, 1))
(COPY_WORD_OP, Destination => (Local_Area, 6), Source => (Param_Area, 2))
(CALL_OP, Params => (Local_Area, 4), Static_Link => (Zero_Base, 5) = Univ_Integer<>, Call_Target => (Zero_Base, 59) = "=?")
(STORE_INT_LIT_OP, Destination => (Local_Area, 5), Int_Value => 4)
(CALL_OP, Params => (Local_Area, 3), Static_Link => (Zero_Base, 30) = Ordering<>, Call_Target => (Zero_Base, 19) = "to_bool")
(IF_OP, If_Source => (Local_Area, 3), If_Condition => 2, Skip_If_False => 4)
(COPY_WORD_OP, Destination => (Local_Area, 3), Source => (Param_Area, 1))
(COPY_WORD_OP, Destination => (Param_Area, 0), Source => (Local_Area, 3))
(RETURN_OP)
(SKIP_OP, Skip_Count => 3)
(COPY_WORD_OP, Destination => (Local_Area, 3), Source => (Param_Area, 2))
(COPY_WORD_OP, Destination => (Param_Area, 0), Source => (Local_Area, 3))
(RETURN_OP)

After code generation and a pass through LLVM’s optimizer this becomes

define void @Max(i64* %_Static_Link, i64* %_Param_Area) {
  %_source1 = getelementptr inbounds i64* %_Param_Area, i64 1
  %_source_val1 = load i64* %_source1, align 8
  %_source2 = getelementptr inbounds i64* %_Param_Area, i64 2
  %_source_val2 = load i64* %_source2, align 8
  %_result3 = icmp sgt i64 %_source_val1, %_source_val2
  br i1 %_result3, label %_lbl7, label %_lbl11

_lbl7:                                            ; preds = %0
  store i64 %_source_val1, i64* %_Param_Area, align 8
  ret void

_lbl11:                                           ; preds = %0
  store i64 %_source_val2, i64* %_Param_Area, align 8
  ret void
}

And from there, LLVM can generate machine code for many architectures.

The next steps are to enable calls to built-in functions, handle types other than Univ_Integer and Univ_Real, and implement Parallel Calls.

We plan to make more frequent releases this summer than in the past.

Stay tuned for more updates on the state of the compiler.