User Tools

Site Tools


compilers:erlang_to_llvm
Return to Home page

From Erlang to LLVM

Abstract

The project goal was to develop a compiler for a subset of Erlang (miniErlang) that generates LLVM IR in human-readable format, built using JFlex and CUP.

Results achieved

  • Implementation of a mini virtual machine (Erlang is based on the BEAM VM):
    • BIFs (built-in functions):
      • is_atom/1
      • is_boolean/1
      • is_float/1
      • is_integer/1
      • is_integer/1
      • is_function/1
      • is_list/1
      • is_number/1
      • abs/1
      • float/1
      • hd/1
      • tl/1
      • length/1
      • round/1
      • trunc/1
    • Other functions:
      • io:format/1, io:format/2
      • lists:nth/1
      • lists:append/2
  • Language
    • Terms: Number, List, Atom, Boolean
    • Expressions:
    • Arithmetic operations
      • Sum (e.g. A + B),
      • Subtraction (e.g. A - B)
      • Sign inversion (e.g. - B)
      • Multiplication (e.g. A * B)
      • Division (e.g. A / B)
      • Integer division (e.g. A div B)
      • Modulo (e.g. A rem B)
    • Comparison operations
      • Exactly equal (e.g. A =:= B)
      • Equal (e.g. A == B)
      • Exactly not equal (e.g. A =/= B)
      • Not equal (e.g. A /= B)
      • Less than (e.g. A < B)
      • Less than or equal (e.g. A =< B)
      • Greater than (e.g. A > B)
      • Greater than or equal (e.g. A >= B)
    • Boolean operations
      • And (e.g. A and B)
      • Or (e.g. A or B)
      • Xor (e.g. A xor B)
      • Not (e.g. not A)
    • List append (e.g. A ++ B)
    • Pattern Matching:
      • Single variable
      • List based (Only available using the match operator, not in functions)
  • Function structures (one parameter):
    • Function clauses
    • Function clauses with guards

miniErlang VM

The miniErlang VM is written in C++, it implements the basic data item construct used in every operation, BIFs (Built-in Functions) and functions needed to support Erlang language features, such as the fact that is dynamically typed. The miniErlang VM is stored in the project folder in two formats: C++ for compiler development, LLVM IR for compiler use; when compiling Erlang code, the latter is combined with the output of the compiler. The code that implements it is very verbose (results in 1k LOC) due to the many error handling conditions, for this reason only the most interesting aspects will be reported.

Literal Struct

It is the basic data item object, it handles typing and any operation that can be performed with basic data item.

Following, a small part of the implementation that should give an idea of how it works:

  1. typedef enum
  2. {
  3. Integer,
  4. Float,
  5. List,
  6. Atom,
  7. Undefined,
  8. Boolean
  9. } LiteralType;
  10.  
  11. typedef struct Literal
  12. {
  13. LiteralType type = Undefined;
  14. void *ptr = nullptr;
  15.  
  16. Literal(int value) : type(Integer), ptr(new int(value))
  17. {
  18. }
  19. Literal(double value) : type(Float), ptr(new double(value)) {}
  20. Literal(size_t value) : type(Atom), ptr(new size_t(value)) {}
  21. Literal(bool value) : type(Boolean), ptr(new bool(value)) {}
  22. Literal(list<Literal> value) : type(List)
  23. {
  24. if (value.size() == 0)
  25. {
  26. ptr = nullptr;
  27. }
  28. else
  29. {
  30. if (value.begin()->type == Undefined)
  31. {
  32. error("undefined expression in list initialization: not allowed.");
  33. }
  34.  
  35. ptr = new pair<Literal, Literal>(*value.begin(), list<Literal>(next(value.begin()), value.end()));
  36. }
  37. }
  38. Literal(Literal head, Literal tail) : type(List)
  39. {
  40. if (head.type == Undefined || tail.type == Undefined)
  41. {
  42. error("undefined expression in list initialization is not allowed.");
  43. }
  44. ptr = new pair<Literal, Literal>(head, tail);
  45. }
  46. Literal() : type(Undefined) {}
  47.  
  48. /* Copy constructor */
  49. Literal(const Literal &a)
  50. {
  51. this->type = a.type;
  52. switch (this->type)
  53. {
  54. case Integer:
  55. this->ptr = new int(*(int *)a.ptr);
  56. break;
  57. case Float:
  58. this->ptr = new double(*(double *)a.ptr);
  59. break;
  60. case List:
  61. this->ptr = a.ptr != nullptr ? new pair<Literal, Literal>(*(pair<Literal, Literal> *)a.ptr) : nullptr;
  62. break;
  63. case Atom:
  64. this->ptr = new size_t(*(size_t *)a.ptr);
  65. break;
  66. case Boolean:
  67. this->ptr = new bool(*(bool *)a.ptr);
  68. break;
  69. case Undefined:
  70. error("bad copy.");
  71. }
  72. }
  73.  
  74. void match(const Literal &match_var)
  75. {
  76. if (this->type == Undefined)
  77. {
  78. this->type = match_var.type;
  79. switch (this->type)
  80. {
  81. case Integer:
  82. this->ptr = new int(*(int *)match_var.ptr);
  83. break;
  84. case Float:
  85. this->ptr = new double(*(double *)match_var.ptr);
  86. break;
  87. case List:
  88. this->ptr = match_var.ptr != nullptr ? new pair<Literal, Literal>(*(pair<Literal, Literal> *)match_var.ptr) : nullptr;
  89.  
  90. break;
  91. case Atom:
  92. this->ptr = new size_t(*(size_t *)match_var.ptr);
  93. break;
  94. case Boolean:
  95. this->ptr = new bool(*(bool *)match_var.ptr);
  96. break;
  97. case Undefined:
  98. error("bad matching");
  99. }
  100. }
  101.  
  102. if (*this != match_var)
  103. {
  104. error("bad matching");
  105. }
  106. }
  107.  
  108. bool try_match(const Literal &match_var)
  109. {
  110. try
  111. {
  112. match(match_var);
  113. }
  114. catch (invalid_argument e)
  115. {
  116. return false;
  117. }
  118. return true;
  119. }
  120. int getInt() const
  121. {
  122. if (type != Integer)
  123. {
  124. error("Type error.");
  125. }
  126.  
  127. int result = *(int *)this->ptr;
  128. return result;
  129. }
  130.  
  131. double getFloat() const
  132. {
  133. if (type != Float)
  134. error("Type error.");
  135. double result = *(double *)this->ptr;
  136. return result;
  137. }
  138.  
  139. list<Literal> getList() const
  140. {
  141. if (type != List)
  142. error("bad matching: not a list.");
  143. list<Literal> result;
  144. if (ptr != nullptr)
  145. {
  146. pair<Literal, Literal> element = *(pair<Literal, Literal> *)ptr;
  147. result.push_back(element.first);
  148. void *iterator = element.second.ptr;
  149. while (iterator != nullptr && element.second.type == List)
  150. {
  151. element = *(pair<Literal, Literal> *)iterator;
  152. result.push_back(element.first);
  153. iterator = element.second.ptr;
  154. }
  155. }
  156. return result;
  157. }
  158.  
  159. size_t getAtom() const
  160. {
  161. if (type != Atom)
  162. error("Type error.");
  163. size_t result = *(size_t *)this->ptr;
  164. return result;
  165. }
  166.  
  167. bool getBoolean() const
  168. {
  169. if (type != Boolean)
  170. error("Type error.");
  171. bool result = *(bool *)this->ptr;
  172. return result;
  173. }
  174. }

Erlang standard functions

float/1 impelementation

float/1 is a built in function, that given a Number as a parameter, return its equivalent but with floating-point representation.

  1. Literal BIF_float(const Literal &l)
  2. {
  3. if (!l.isNumber())
  4. {
  5. error("float can only be applied to numbers.");
  6. }
  7. if (l.type == Integer)
  8. {
  9. return (double)l.getInt();
  10. }
  11. return l;
  12. }

io:format/2 implementation

It equivalent in some ways to C's printf, supports in a limited way ~s and ~w control sequences (https://erlang.org/doc/man/io.html#format-2).

io:format/2 example:

  1. io:format("Number one: ~w, \"hello\" string: ~s, \"hello\" list representation: ~w ~n", [1, "hello", "hello"]).
  2. % outputs 'Number one: 1, "hello" string: hello, "hello" list representation: [104,101,108,108,111] ~n\n"
  3.  
  4. Implementation:
  5. <code C++[enable_line_numbers="true"]>
  6. Literal ioformat(const Literal &format, const Literal &data)
  7. {
  8. if (format.type != List || data.type != List)
  9. {
  10. error("bad argument\n\tin function io:format: needs 2 list parameters (format and data).");
  11. }
  12.  
  13. list<Literal> llist = data.getList();
  14.  
  15. regex n("(([^~]|^)(~n))");
  16. regex ee("(([^~]|^)~(w|s))");
  17.  
  18. string ss = format.getString('s');
  19. ss = regex_replace(ss, n, "$2\n");
  20.  
  21. smatch mm;
  22.  
  23. string to_print = "";
  24.  
  25. auto llist_it = llist.begin();
  26. int i = 0;
  27. while (regex_search(ss, mm, ee))
  28. {
  29. if (i++ >= llist.size())
  30. {
  31. error("bad argument\n\tin function io:format: data control sequences are more than elements in data list.");
  32. }
  33. to_print += mm.prefix().str() + mm.format("$2");
  34. if (mm.format("$3").compare("w") == 0)
  35. {
  36. if (llist_it->type == List)
  37. {
  38. to_print += "[" + llist_it->getString('w') + "]";
  39. }
  40. else
  41. {
  42. to_print += llist_it->getString('w');
  43. }
  44. }
  45. else
  46. {
  47. to_print += llist_it->getString('s');
  48. }
  49.  
  50. llist_it = next(llist_it);
  51. ss = mm.suffix().str();
  52. }
  53.  
  54. if (i < llist.size())
  55. {
  56. error("bad argument\n\tin function io:format: data control sequences are less than elements in data list.");
  57. }
  58.  
  59. cout << to_print << ss;
  60.  
  61. return Literal(true);
  62. }

++ operator and lists:append/2 implementation

++ and lists:append/2 concatenate two lists.

Example usage of the ++ operator: ListA ++ ListB.

Usage of lists:append/2: lists:append(ListA, ListB).

Implementation:

  1. Literal listsappend(const Literal &a, const Literal &b)
  2. {
  3. if (a.type != List || b.type != List)
  4. {
  5. error("bad argument\n\tin function lists:append: needs 2 list parameters (a and b).");
  6. }
  7. if (!a.isProperList() || !b.isProperList())
  8. {
  9. error("bad argument\n\tin function lists:append: improper lists are not supported.");
  10. }
  11.  
  12. list<Literal> concatenation = a.getList();
  13. list<Literal> b_list = b.getList();
  14. concatenation.insert(concatenation.end(), b_list.begin(), b_list.end());
  15.  
  16. return Literal(concatenation);
  17. }

Compiler

The compiler is composed of a scanner (generated by JFlex) and a parser (generated by CUP), every time the scanner recognizes a symbol it passes it to the parser. The Symbol class holds information about each recognized symbol.

Scanner

The scanner is produced using jFlex (a lexical analyzer generator written in Java). JFlex is designed to work together with the LALR parser generator CUP.

  1. nl = \r|\n|\r\n
  2. ws = [ \t]
  3.  
  4. %%
  5.  
  6. /* Symbols */
  7. "(" { return symbol(sym.ROUND_OPEN); }
  8. ")" { return symbol(sym.ROUND_CLOSE); }
  9. "[" { return symbol(sym.SQUARE_OPEN); }
  10. "]" { return symbol(sym.SQUARE_CLOSE); }
  11. "{" { return symbol(sym.BRACE_OPEN); }
  12. "}" { return symbol(sym.BRACE_CLOSE); }
  13. "/" { return symbol(sym.SLASH); }
  14. "." { return symbol(sym.DOT); }
  15. "," { return symbol(sym.COMMA); }
  16. ":" { return symbol(sym.COLON); }
  17. ";" { return symbol(sym.SEMICOLON); }
  18. "=" { return symbol(sym.MATCH); }
  19. "|" { return symbol(sym.VERTICAL_BAR); }
  20. "!" { return symbol(sym.NOT); }
  21. "-" { return symbol(sym.HYPHEN); }
  22. "+" { return symbol(sym.PLUS); }
  23. "++" { return symbol(sym.PLUS_PLUS); }
  24. "*" { return symbol(sym.STAR); }
  25. "->" { return symbol(sym.RIGHT_ARROW); }
  26. "<-" { return symbol(sym.LEFT_ARROW); }
  27. "==" { return symbol(sym.EQ); }
  28. "=:=" { return symbol(sym.EXACT_EQ); }
  29. "/=" { return symbol(sym.NOT_EQ); }
  30. "=/=" { return symbol(sym.EXACT_NOT_EQ); }
  31. "<" { return symbol(sym.LESS); }
  32. "=<" { return symbol(sym.LESS_EQ); }
  33. ">" { return symbol(sym.GREATER); }
  34. ">=" { return symbol(sym.GREATER_EQ); }
  35.  
  36.  
  37. /* Keywords */
  38. "and" { return symbol(sym.K_AND); }
  39. "not" { return symbol(sym.K_NOT); }
  40. "or" { return symbol(sym.K_OR); }
  41. "xor" { return symbol(sym.K_XOR); }
  42. "div" { return symbol(sym.K_DIV); }
  43. "rem" { return symbol(sym.K_REM); }
  44. "when" { return symbol(sym.K_WHEN); }
  45.  
  46. /* Boolean terms */
  47. "false" { return new Symbol(sym.BOOLEAN, yyline, yycolumn, new String(yytext())); }
  48. "true" { return new Symbol(sym.BOOLEAN, yyline, yycolumn, new String(yytext())); }
  49.  
  50. /* String term */
  51. [\"]([^\"\\]|\\.)*[\"] { return new Symbol(sym.STRING, yyline, yycolumn, new String(yytext().substring(1, yytext().length() - 1))); }
  52.  
  53. /* Variable names */
  54. [A-Z_][0-9a-zA-Z_@]* { return new Symbol(sym.VARIABLE, yyline, yycolumn, new String(yytext())); }
  55.  
  56. /* Atom terms */
  57. [a-z][0-9a-zA-Z_@]* { return new Symbol(sym.ATOM, yyline, yycolumn, new String(yytext())); }
  58. [\']([^\'\\]|\\.)*[\'] { return new Symbol(sym.ATOM, yyline, yycolumn, new String(yytext().substring(1, yytext().length() - 1))); }
  59.  
  60. /* Float terms */
  61. [0-9]*\.[0-9]+ { return new Symbol(sym.FLOAT, yyline, yycolumn, new Float(yytext())); }
  62.  
  63. /* Integer terms */
  64. [1-9][0-9]*|0 { return new Symbol(sym.INT, yyline, yycolumn, new Integer(yytext())); }
  65.  
  66. /* Comments */
  67. "%" [^\r\n]* {nl}? { ; }
  68.  
  69. {ws}|{nl} { ; }
  70.  
  71. . { System.out.println("SCANNER ERROR: "+yytext()); }

Parser

The parser generator is written in CUP, the code is generated by Java classes, one for each language item.

Grammar start

Erlang does not support global variables, nor expressions that are not part of a function, thus the program must start with a function definition.

  1. start with program;
  2.  
  3. program ::= function_seq:funs {:
  4. funs.generateCode(manager, null);
  5. manager.checkUndefinedFunctionsCalls();
  6. if (sem() && parser.semErrors == 0) {
  7. System.out.println(parser.outputBuffer);
  8. } else {
  9. System.err.println("\nOUTPUT COULD NOT BE PRODUCED DUE TO ERRORS\n");
  10. }
  11. System.err.println(parser.errorBuffer);
  12.  
  13. System.err.println("######################");
  14. System.err.println("Syntax Warnings : " + parser.synWarnings);
  15. System.err.println("Semantic Errors : " + parser.semErrors);
  16. System.err.println("Semantic Warnings: " + parser.semWarnings);
  17. :};
  18.  
  19. function_seq ::=
  20. function_seq:funSeq function:fun {: RESULT = new FunctionSequence(funSeq, fun); :}
  21. | function:fun {: RESULT = new FunctionSequence(fun); :}
  22. ;

The Manager class is a wrapper to access the parser, it is used by every class corresponding to a non terminal. On line 4 of the above code, the Manager is used to check whether there where calls to functions that are have not been defined, either in the file being compiled or in the miniErlang VM.

Every non terminal used in the parser has an equivalent class defined with these common methods:

  • generateCode(): called by its parent to generate the corresponding LLVM IR code;
  • destructDependencies(): deallocates every object instated by the child non terminals;
  • destruct(): that calls destructDependencies() and deallocates every object instatiated in by the non terminal;

and common attributes:

  • subgraphSize: the size of the code produced by generateCode();
  • label: the LLVM IR label used to store the object resulting from the operations performed in generateCode().

FunctionSequence Class:

  1. public class FunctionSequence extends Node {
  2. FunctionSequence seqHead;
  3. Function tail;
  4.  
  5. public FunctionSequence(Function tail) {
  6. this.tail = tail;
  7. seqHead = null;
  8. }
  9. public FunctionSequence(FunctionSequence head, Function tail) {
  10. seqHead = head;
  11. this.tail = tail;
  12. }
  13.  
  14. public void generateCode(Manager manager, Node parent) {
  15. super.generateCode(manager, parent);
  16. if(seqHead != null) {
  17. seqHead.generateCode(manager, this);
  18. }
  19. tail.generateCode(manager, this);
  20. }
  21.  
  22. public long destruct(Manager manager, Node caller) {
  23. return 0;
  24.  
  25. }
  26. public long destructDependencies(Manager manager, Node caller) {
  27. return 0;
  28. }
  29.  
  30. }

Functions

Due to the complexity derived from implementation details of the miniErlang VM, functions clauses can have at most 1 argument.

  1. function ::=
  2. function_clause:head function_clause_seq:tail {: RESULT = new Function(head, tail); :}
  3. | function_clause:head error {: syntaxError("Invalid function definition."); :}
  4. ;
  5.  
  6. function_clause_seq ::=
  7. SEMICOLON function_clause:head function_clause_seq:tail {: RESULT = new FunctionClauseSequence(head, tail); :}
  8. | DOT {: RESULT = null; :}
  9.  
  10. ;
  11.  
  12. function_clause ::=
  13. ATOM:name argument:arg RIGHT_ARROW expression_seq:expressionSeq {: RESULT = new FunctionClause(name, arg, expressionSeq); :}
  14. | ATOM:name argument:arg K_WHEN guard:g RIGHT_ARROW expression_seq:expressionSeq {: RESULT = new FunctionClause(name, arg, g, expressionSeq); :}
  15. | error argument RIGHT_ARROW expression_seq {: syntaxError("Invalid function name."); :}
  16. | error argument K_WHEN guard RIGHT_ARROW expression_seq {: syntaxError("Invalid function name."); :}
  17. | ATOM error RIGHT_ARROW expression_seq {: syntaxError("Invalid function clause argument."); :}
  18. | ATOM error K_WHEN guard RIGHT_ARROW expression_seq {: syntaxError("Invalid function clause argument."); :}
  19. | ATOM argument RIGHT_ARROW error {: syntaxError("Invalid function clause body."); :}
  20. | ATOM argument K_WHEN guard RIGHT_ARROW error {: syntaxError("Invalid function clause body."); :}
  21. | ATOM argument K_WHEN error RIGHT_ARROW expression_seq {: syntaxError("Invalid function clause guard."); :}
  22. ;
  23.  
  24. argument ::=
  25. ROUND_OPEN expression:arg ROUND_CLOSE {: RESULT = arg; :}
  26. | ROUND_OPEN ROUND_CLOSE {: RESULT = null; :}
  27. ;
  28.  
  29. guard ::=
  30. expression:head guard_tail:tail {: RESULT = new Guard(new AltList(head, tail)); :}
  31. ;
  32. guard_tail ::=
  33. COMMA expression:head guard_tail:tail {: RESULT = new AltList(head, tail); :}
  34. | {: RESULT = null; :}
  35. ;

The Function class handles generating the function firm and the code that throws an error if no matched was found between the function parameter and the function clauses. Function.generateCode():

  1. public void generateCode(Manager manager, Node parent) {
  2. super.generateCode(manager, parent);
  3.  
  4. manager.checkTailMatch(head, tail);
  5. manager.setFunctionName(manager.getFunctionName(head.name, head.argument));
  6. manager.openClause();
  7.  
  8. long returnLabel = manager.genLabel();
  9. manager.setReturnLabel(returnLabel);
  10.  
  11. if (head.argument != null) {
  12. long parameterLabel = manager.genLabel();
  13. manager.setParameterLabel(parameterLabel);
  14. manager.dumpFormatln(
  15. "define void %s(%%%s* noalias sret align 8 %%%d, %%%s* %%%d) #0 personality i8*"
  16. + " bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {",
  17. manager.getFunctionName(),
  18. Const.LITERAL_STRUCT,
  19. returnLabel,
  20. Const.LITERAL_STRUCT,
  21. parameterLabel);
  22. } else {
  23. manager.dumpFormatln(
  24. "define void %s(%%%s* noalias sret align 8 %%%d) #0 personality i8* bitcast (i32"
  25. + " (...)* @__gxx_personality_v0 to i8*) {",
  26. manager.getFunctionName(), Const.LITERAL_STRUCT, returnLabel);
  27. }
  28. manager.genLabel();
  29. long returnPointerLabel = manager.genLabel();
  30. manager.dumpFormatln("\t%%%d = alloca i8*, align 8", returnPointerLabel);
  31. long bitcastReturnPointerLabel = manager.genLabel();
  32.  
  33. manager.dumpFormatln(
  34. "\t%%%d = bitcast %%%s* %%%d to i8*",
  35. bitcastReturnPointerLabel, Const.LITERAL_STRUCT, returnLabel);
  36. manager.dumpFormatln(
  37. "\tstore i8* %%%d, i8** %%%d, align 8", bitcastReturnPointerLabel, returnPointerLabel);
  38.  
  39. long resumePointerLabel = manager.genLabel();
  40. manager.setResumePointer(resumePointerLabel);
  41. long resumeIntegerLabel = manager.genLabel();
  42. manager.setResumeInteger(resumeIntegerLabel);
  43. manager.dumpFormatln("\t%%%d = alloca i8*, align 8", resumePointerLabel);
  44. manager.dumpFormatln("\t%%%d = alloca i32, align 4", resumeIntegerLabel);
  45.  
  46. head.generateCode(manager, this);
  47. if (tail != null) {
  48. manager.dumpCodeLabel();
  49. tail.generateCode(manager, this);
  50. }
  51.  
  52. if (head.argument != null) {
  53. manager.dumpCodeLabel();
  54. manager.dumpFormatln("\tcall void %s()", Const.BAD_MATCHING_ERROR);
  55. manager.dumpln("\tret void");
  56. }
  57. manager.dumpln("}\n");
  58. manager.popFunctionSymbols();
  59. }

FunctionClauseSequence is very similar in nature to FunctionSequence as it just generates the list of FunctionClauses.

FunctionClause handles function clauses with: no parameter, 1 parameter and with guards. If the parameter is a constant term, the generator will match the run-time parameter with the term declared in the function clause. If on the other hand the parameter is a variable, its name will be bound to the LLVM IR label previously set by the Function class.

The subgraphSize attribute of the child non terminals is used to compute the label the next clause will be at, that will need to be evaluated if the current function clause doesn't match the run-time parameter.

FunctionClause.generateCode():

  1. public void generateCode(Manager manager, Node parent) {
  2. this.parent = parent;
  3.  
  4. if (argument != null) {
  5. if (argument instanceof Variable) {
  6. Variable variableArgument = (Variable) argument;
  7. variableArgument.generateCode(manager, this, manager.getParameterLabel());
  8. } else {
  9. // Check that runtime argument is equal to function-def argument.
  10. argument.generateCode(manager, this);
  11.  
  12. manager.dumpCodeLabel();
  13. long matchingLabel = manager.genLabel();
  14. manager.dumpFormatln(
  15. "\t%%%d = invoke zeroext i1 %s(%%%s* %%%d, %%%s* nonnull align 8"
  16. + " dereferenceable(16) %%%d)",
  17. matchingLabel,
  18. Const.LITERAL_CLAUSE_MATCH,
  19. Const.LITERAL_STRUCT,
  20. manager.getParameterLabel(),
  21. Const.LITERAL_STRUCT,
  22. argument.label);
  23.  
  24. long unwindLabel = matchingLabel + 1;
  25. long branchLabel = unwindLabel + CLEANUP_LABEL_SIZE + RESUME_LABEL_SIZE;
  26. manager.dumpFormatln("\t\tto label %%%d unwind label %%%d", branchLabel, unwindLabel);
  27.  
  28. manager.cleanupError();
  29. argument.destruct(manager, this);
  30. manager.resumeError();
  31. long rbl = manager.genLabel();
  32. manager.dumpln(branchLabel + ":");
  33. argument.destruct(manager, this);
  34. long clauseExpressions = branchLabel + 1;
  35. long nextClause = branchLabel + 2 + expressions.subgraphSize;
  36. manager.dumpFormatln(
  37. "\tbr i1 %%%d, label %%%d, label %%%d", matchingLabel, clauseExpressions, nextClause);
  38. manager.dumpCodeLabel();
  39. }
  40. }
  41. if (guard != null) {
  42. guard.generateCode(manager, this);
  43. manager.dumpCodeLabel();
  44.  
  45. long clauseExpressions = manager.getCurrentLabel();
  46. long nextClause = manager.getCurrentLabel() + 1 + expressions.subgraphSize;
  47. manager.dumpFormatln(
  48. "\tbr i1 %%%d, label %%%d, label %%%d", guard.label, clauseExpressions, nextClause);
  49. manager.dumpCodeLabel();
  50. }
  51. expressions.generateCode(manager, this);
  52. expressions.generateReturn(manager);
  53. manager.closeClause();
  54. }
Guards

A guard is a series of guard expressions separated by a comma. Guards can be used to perform simple tests and comparisons on the variables in a pattern; they can be used in function defintions to expand the power of pattern matching.

The optional guard of the function clause is implemented by evaluating every condition, storing each into a list, and passing the list to the eval_guard() function, implemented in the miniErlang VM.

Guard.generateCode():

  1. public void generateCode(Manager manager, Node parent) {
  2. super.generateCode(manager, parent);
  3.  
  4. this.checkGuardSemantic(manager);
  5. guard_expression.generateCode(manager, this);
  6. manager.dumpCodeLabel();
  7. label = manager.genLabel();
  8. manager.dumpFormatln("%%%d = invoke zeroext i1 %s(%%%s* %%%d)",
  9. label, Const.EVAL_GUARD, Const.LITERAL_STRUCT, guard_expression.label);
  10. long afterUnwind = manager.getCurrentLabel() + CLEANUP_LABEL_SIZE + RESUME_LABEL_SIZE;
  11. manager.dumpFormatln("\t\tto label %%%d unwind label %%%d", afterUnwind, manager.getCurrentLabel());
  12. manager.cleanupError();
  13. destructDependencies(manager, this);
  14. manager.resumeError();
  15. }

Terms

Terms are the basic data object usable in Erlang, their implementation is trivial: it requires calling the Literal struct constructor relative to the type of object that is needed.

  1. term ::=
  2. ATOM:value {: RESULT = new Atom(value); :}
  3. | FLOAT:value {: RESULT = new minierlang.exp.terms.Number(value); :}
  4. | INT:value {: RESULT = new minierlang.exp.terms.Number(value); :}
  5. | BOOLEAN:value {: RESULT = new Bool(value); :}
  6. | STRING:value {: RESULT = new List(value); :}
  7. | non_empty_list:value {: RESULT = value; :}
  8. | empty_list:value {: RESULT = value; :}
  9. ;
  10.  
  11. empty_list ::=
  12. SQUARE_OPEN SQUARE_CLOSE {: RESULT = new List(null, null); :}
  13. ;
  14.  
  15. non_empty_list ::=
  16. normal_list:list {: RESULT = list; :}
  17. | alt_list:list {: RESULT = list; :}
  18. ;
  19. normal_list ::=
  20. SQUARE_OPEN expression:head normal_list_tail:tail {: RESULT = new AltList(head, tail); :}
  21. ;
  22. normal_list_tail ::=
  23. COMMA expression:head normal_list_tail:tail {: RESULT = new AltList(head, tail); :}
  24. | SQUARE_CLOSE {: RESULT = null; :}
  25. ;
  26.  
  27. alt_list ::=
  28. SQUARE_OPEN expression:head alt_list_tail:tail SQUARE_CLOSE {: RESULT = new AltList(head, tail); :}
  29. | SQUARE_OPEN expression:head VERTICAL_BAR expression:tail SQUARE_CLOSE {: RESULT = new AltList(head, tail); :}
  30. ;
  31. alt_list_tail ::=
  32. COMMA expression:head alt_list_tail:tail {: RESULT = new AltList(head, tail); :}
  33. | VERTICAL_BAR expression:actual_tail {: RESULT = actual_tail; :}
  34. ;
Atoms

Atoms are used to represent different non-numerical constant values; they start with lowercase letters, followed by a sequence of alphanumeric characters or _, or @.

Atoms in the miniErlang VM are represented as long unsigned integers, since two atoms can be either equal equal or not (i.e. one can't be greater than the other).

Atom class:

  1. public class Atom extends Term {
  2. private String stringForm;
  3. private long atomId;
  4. public Atom(String atom) {
  5. stringForm = atom;
  6. this.subgraphSize = 1 + Node.CLEANUP_LABEL_SIZE + Node.RESUME_LABEL_SIZE;
  7. }
  8.  
  9. public void generateCode(Manager manager, Node parent) {
  10. super.generateCode(manager, parent);
  11. manager.dumpln("\t; start " + this.getClass().getName());
  12.  
  13. atomId = manager.getAtom(stringForm);
  14. label = allocate(manager);
  15. manager.dumpFormatln(
  16. "\tinvoke void %s(%%%s* %%%d, i64 %d)", Const.LITERAL_CONSTRUCT_ATOM, Const.LITERAL_STRUCT, label, atomId);
  17.  
  18.  
  19. long unwindLabel = label + 1;
  20. long branchLabel = unwindLabel + Node.CLEANUP_LABEL_SIZE + Node.RESUME_LABEL_SIZE;
  21. manager.dumpFormatln("\t\tto label %%%d unwind label %%%d", branchLabel, unwindLabel);
  22.  
  23. manager.cleanupError();
  24. destructDependencies(manager, this);
  25. manager.resumeError();
  26. }
  27. }

Boolean, Integer and Float terms are generated similarly to Atoms, but with a different constructor.

Lists

Lists are created by enclosing the list elements in square brackets; they can contain values of any type.

Lists can be represented in two ways in Erlang:

  • comma separated (e.g. [1, 2, 3, 4]);
  • head tail format (e.g. [1 | [2 | [3 | [4 | []]]]]);

The two representation are equivalent in terms of accessory data structures.

Two classes generate code for lists:

  • List: handles conversion from string to List Literal.
  • AltList: handles recursive list instantiation.

Every AltList must be terminated by an empty List object to maintain representations equivalent.

AltList class:

  1. public class AltList extends Term {
  2. public Expression head;
  3. public Expression tail;
  4.  
  5. public AltList(Expression head, Expression tail) {
  6. this.head = head;
  7. this.tail = (tail == null ? new List("") : tail);
  8. this.subgraphSize =
  9. 3
  10. + CLEANUP_LABEL_SIZE
  11. + RESUME_LABEL_SIZE
  12. + this.head.subgraphSize
  13. + this.tail.subgraphSize;
  14. ;
  15. }
  16.  
  17. public void generateCode(Manager manager, Node parent) {
  18. super.generateCode(manager, parent);
  19. manager.dumpln("\t; start " + this.getClass().getName());
  20.  
  21. head.generateCode(manager, this);
  22. manager.dumpCodeLabel();
  23. tail.generateCode(manager, this);
  24. manager.dumpCodeLabel();
  25.  
  26. label = allocate(manager);
  27. manager.dumpFormatln(
  28. "\tinvoke void %s(%%%s* %%%d, %%%s* %%%d, %%%s* %%%d)",
  29. Const.LITERAL_CONSTRUCT_LIST_ELEMENT,
  30. Const.LITERAL_STRUCT,
  31. label,
  32. Const.LITERAL_STRUCT,
  33. head.label,
  34. Const.LITERAL_STRUCT,
  35. tail.label);
  36. long afterUnwind = manager.getCurrentLabel() + CLEANUP_LABEL_SIZE + RESUME_LABEL_SIZE;
  37. manager.dumpFormatln(
  38. "\t\tto label %%%d unwind label %%%d", afterUnwind, manager.getCurrentLabel());
  39. manager.cleanupError();
  40. destructDependencies(manager, this);
  41. manager.resumeError();
  42. }
  43.  
  44. public long destructDependencies(Manager manager, Node caller) {
  45. long maxParentDep = super.destructDependencies(manager, caller);
  46. if (head != caller) {
  47. if (head.label > maxParentDep) {
  48. maxParentDep = Math.max(head.destruct(manager, this), maxParentDep);
  49. }
  50. if (tail != caller) {
  51. maxParentDep = Math.max(tail.destructDependencies(manager, this), maxParentDep);
  52. }
  53. }
  54.  
  55. return maxParentDep;
  56. }
  57. }

Expressions

In Erlang every instruction (except function definitions) is an expression, and every expression holds an immutable value. The Expression class is inherited by the great majority of all classes in the project.

Grammar rules regarding expressions:

  1. expression ::=
  2. pattern_matching:expr {: RESULT = expr; :}
  3. | term:expr {: RESULT = expr; :}
  4. | VARIABLE:var {: RESULT = new Variable(var); :}
  5. | term_comparison:expr {: RESULT = expr; :}
  6. | arithmetic_expression:expr {: RESULT = expr; :}
  7. | boolean_expression:expr {: RESULT = expr; :}
  8. | function_call:expr {: RESULT = expr; :}
  9. | ROUND_OPEN expression:expr ROUND_CLOSE {: RESULT = expr; :}
  10. | lists_append:expr {: RESULT = expr; :}
  11. ;
  12.  
  13. term_comparison ::=
  14. expression:lhs EQ expression:rhs {: RESULT = new Equals(lhs, rhs); :}
  15. | expression:lhs EXACT_EQ expression:rhs {: RESULT = new ExactEquals(lhs, rhs); :}
  16. | expression:lhs NOT_EQ expression:rhs {: RESULT = new NotEquals(lhs, rhs); :}
  17. | expression:lhs EXACT_NOT_EQ expression:rhs {: RESULT = new ExactNotEquals(lhs, rhs); :}
  18. | expression:lhs LESS expression:rhs {: RESULT = new Less(lhs, rhs); :}
  19. | expression:lhs LESS_EQ expression:rhs {: RESULT = new LessEquals(lhs, rhs); :}
  20. | expression:lhs GREATER expression:rhs {: RESULT = new Greater(lhs, rhs); :}
  21. | expression:lhs GREATER_EQ expression:rhs {: RESULT = new GreaterEquals(lhs, rhs); :}
  22. ;
  23.  
  24. arithmetic_expression ::=
  25. PLUS expression:val {: RESULT = val; :}
  26. | HYPHEN expression:val {: RESULT = new Negative(val); :}
  27. | expression:lhs PLUS expression:rhs {: RESULT = new Add(lhs, rhs); :}
  28. | expression:lhs HYPHEN expression:rhs {: RESULT = new Sub(lhs, rhs); :}
  29. | expression:lhs STAR expression:rhs {: RESULT = new Mul(lhs, rhs); :}
  30. | expression:lhs SLASH expression:rhs {: RESULT = new Div(lhs, rhs); :}
  31. | expression:lhs K_DIV expression:rhs {: RESULT = new IntegerDiv(lhs, rhs); :}
  32. | expression:lhs K_REM expression:rhs {: RESULT = new Rem(lhs, rhs); :}
  33. ;
  34.  
  35. boolean_expression ::=
  36. NOT expression:rhs {: RESULT = new Not(rhs); :}
  37. | expression:lhs K_AND expression:rhs {: RESULT = new And(lhs, rhs); :}
  38. | expression:lhs K_OR expression:rhs {: RESULT = new Or(lhs, rhs); :}
  39. | expression:lhs K_XOR expression:rhs {: RESULT = new Xor(lhs, rhs); :}
  40. ;
Variables

Variables are a special kind of expression, in that they can hold no value (i.e. can be unbounded), but once a value is assigned to them, it cannot be changed; variables in Erlang are bound to values through pattern matching.

Example:

1> X.  ** 1: variable 'X' is unbound **
2> X = 2.
2
3> X + 1.
3
4> X = 3. ** exception error: no match of right hand side value 3
Binary Expressions

Most expression are binary (they operate on 2 expressions), there are three types of binary expressions: right associative, left associative, non associative. The precedence of the operators is defined as following:

  1. // lowest priority
  2. precedence right MATCH;
  3. precedence nonassoc EQ, NOT_EQ, LESS_EQ, LESS, GREATER_EQ, GREATER, EXACT_EQ, EXACT_NOT_EQ;
  4. precedence right PLUS_PLUS;
  5. precedence left PLUS, HYPHEN, K_OR, K_XOR;
  6. precedence left SLASH, STAR, K_DIV, K_REM, K_AND;
  7. precedence nonassoc K_NOT;
  8. precedence nonassoc SHARP;
  9. precedence nonassoc COLON;
  10. // highest priority

Two general classes have been implemented to handle binary expression (as in operations between two expressions):

LeftAssocBinaryExpression:

  1. public abstract class LeftAssocBinaryExpression extends Expression {
  2. protected Expression lhs, rhs;
  3.  
  4. public LeftAssocBinaryExpression(Expression lhs, Expression rhs) {
  5. this.lhs = lhs;
  6. this.rhs = rhs;
  7. subgraphSize = 3 + rhs.subgraphSize + lhs.subgraphSize + CLEANUP_LABEL_SIZE + RESUME_LABEL_SIZE;
  8.  
  9. }
  10.  
  11. public void genericGenerateCode(String function, Manager manager, Node parent) {
  12. super.generateCode(manager, parent);
  13.  
  14. rhs.generateCode(manager, this);
  15. manager.dumpCodeLabel();
  16. lhs.generateCode(manager, this);
  17.  
  18.  
  19. manager.dumpCodeLabel();
  20. label = allocate(manager);
  21. manager.dumpFormatln(
  22. "\tinvoke void %s(%%%s* sret align 8 %%%d, %%%s* %%%d, %%%s* nonnull align 8"
  23. + " dereferenceable(16) %%%d)",
  24. function,
  25. Const.LITERAL_STRUCT,
  26. label,
  27. Const.LITERAL_STRUCT,
  28. lhs.label,
  29. Const.LITERAL_STRUCT,
  30. rhs.label);
  31.  
  32. long unwindLabel = label + 1;
  33. long branchLabel = unwindLabel + Node.CLEANUP_LABEL_SIZE + Node.RESUME_LABEL_SIZE;
  34. manager.dumpFormatln("\t\tto label %%%d unwind label %%%d", branchLabel, unwindLabel);
  35.  
  36. manager.cleanupError();
  37. destructDependencies(manager, this);
  38. manager.resumeError();
  39. }
  40.  
  41.  
  42. public long destructDependencies(Manager manager, Node caller) {
  43. long maxParentDep = super.destructDependencies(manager, caller);
  44. if (rhs != caller) {
  45. if (rhs.label >= maxParentDep) {
  46. manager.dumpln("\t; l rhs (" + rhs.label + ") maxdep (" + maxParentDep + ")");
  47. maxParentDep = Math.max(rhs.destruct(manager, this), maxParentDep);
  48. }
  49. if (lhs != caller && lhs.label >= maxParentDep) {
  50. manager.dumpln("\t; l lhs (" + lhs.label + ") maxdep (" + maxParentDep + ")");
  51. maxParentDep = Math.max(lhs.destruct(manager, this), maxParentDep);
  52. }
  53. }
  54.  
  55. return maxParentDep;
  56. }
  57. }

This class is inherited by every left associative operation. The class for right associative operations is very similar, but inverts the order of the code generation of its dependencies.

Example of LeftAssociative class (Add):

  1. public class Add extends LeftAssocBinaryExpression {
  2. public Add(Expression lhs, Expression rhs) {
  3. super(lhs, rhs);
  4. }
  5.  
  6. public void generateCode(Manager manager, Node parent) {
  7. manager.dumpln("\t; start " + this.getClass().getName() + " (" + subgraphSize + ")");
  8. super.genericGenerateCode(Const.LITERAL_ADD, manager, parent);
  9. }
  10. }
Function Calls

Function calls are very simple expressions, their name can include the module from which they come from.

  1. function_call ::=
  2. ATOM:function_name ROUND_OPEN ROUND_CLOSE {: RESULT = new FunctionCall(function_name, null); :}
  3. | ATOM:function_name ROUND_OPEN expression_seq:parameters ROUND_CLOSE {: RESULT = new FunctionCall(function_name, parameters); :}
  4. | ATOM:module COLON ATOM:function_name ROUND_OPEN expression_seq:parameters ROUND_CLOSE {: RESULT = new FunctionCall(module + "." + function_name, parameters); :}
  5. | ATOM:function_name ROUND_OPEN error {: syntaxError("Invalid function call."); :}
  6. ;

The functionCall class, translates the function name given as input into LLVM IR equivalent, and prints the relative parameters. FunctionCall.generateCode()

  1. public void generateCode(Manager manager, Node parent) {
  2. super.generateCode(manager, parent);
  3.  
  4. manager.recordFunctionCall(name, parameters);
  5.  
  6.  
  7. if (parameters != null) {
  8. parameters.generateCode(manager, this);
  9. manager.dumpCodeLabel();
  10. label = allocate(manager);
  11. manager.dump(
  12. String.format(
  13. "\tinvoke void %s(%%%s* sret align 8 %%%d",
  14. manager.getFunctionName(name, parameters), Const.LITERAL_STRUCT, label));
  15.  
  16. ExpressionSequence dfs_node = parameters;
  17. while (dfs_node != null) {
  18. manager.dump(String.format(", %%%s* %%%d", Const.LITERAL_STRUCT, dfs_node.head.label));
  19. dfs_node = dfs_node.tail;
  20. }
  21. manager.dumpln(")");
  22.  
  23. } else {
  24. label = allocate(manager);
  25. manager.dumpFormatln(
  26. "\tinvoke void %s(%%%s* sret align 8 %%%d)",
  27. manager.getFunctionName(name, parameters), Const.LITERAL_STRUCT, label);
  28. }
  29.  
  30. long unwindLabel = manager.getCurrentLabel(),
  31. branchLabel = unwindLabel + Node.CLEANUP_LABEL_SIZE + Node.RESUME_LABEL_SIZE;
  32.  
  33. manager.dumpFormatln("\t\tto label %%%d unwind label %%%d", branchLabel, unwindLabel);
  34.  
  35. manager.cleanupError();
  36. destructDependencies(manager, this);
  37. manager.resumeError();
  38. }

The ++ operator is supported through the lists_append non terminal, that simply translates it into a call to the function 'lists:append':

  1. lists_append ::=
  2. expression:a PLUS_PLUS expression:b {: RESULT = new FunctionCall("lists.append", new ExpressionSequence(a, new ExpressionSequence(b, null))); :}
  3. ;

Pattern Matching

This is the most complex feature of Erlang: In a pattern matching expression, a left-hand side pattern is matched against a right-hand side term. If the matching succeeds, any unbound variables in the pattern become bound. If the matching fails, a run-time error occurs.

In this project, pattern matching was implemented for the match operator (=) only, it is not supported in function clauses, since that are inherently more complex to handle.

The following action code distinguishes between expressions with left-hand side pattern that is List and those that aren't, since lists can carry with them more than one variable to bound, and thus recursive behavior.

  1. pattern_matching ::=
  2. expression:lhs MATCH expression:rhs {: RESULT = lhs instanceof AltList ? new ListMatching((AltList)lhs, rhs) : new Match(lhs, rhs); :}
  3. | expression MATCH error {: syntaxError("Invalid match operation."); :}
  4. | error MATCH expression {: syntaxError("Invalid match operation."); :}
  5. ;

The Match class is similar to other binary expressions such as the Add illustrated previously.

ListMatching is the most complex class of the entire compiler, because it has to handle complex pattern matching (e.g. [First, Second, [HeadOfThird | TailOfThird]] = [1, 2, [3, 4, 5]]);

ListMatching Class:

  1. public class ListMatching extends Expression {
  2. static long temporaryLabel = 0;
  3. AltList lhs;
  4. Expression rhs;
  5. Expression headMatch, tailMatch;
  6.  
  7. public ListMatching(AltList lhs, Expression rhs) {
  8. // User code can't declare variables starting with a lowercase letter, so there can't be any
  9. // collision.
  10. long currentTemporaryLabel = temporaryLabel++;
  11. this.rhs = new Match(new Variable("tmp" + currentTemporaryLabel), rhs);
  12. headMatch =
  13. lhs.head instanceof AltList
  14. ? new ListMatching(
  15. (AltList) lhs.head,
  16. new FunctionCall(
  17. "hd",
  18. new ExpressionSequence(new Variable("tmp" + currentTemporaryLabel), null)))
  19. : new Match(
  20. lhs.head,
  21. new FunctionCall(
  22. "hd",
  23. new ExpressionSequence(new Variable("tmp" + currentTemporaryLabel), null)));
  24. if (lhs.tail != null && lhs.tail instanceof AltList) {
  25. tailMatch =
  26. new ListMatching(
  27. (AltList) lhs.tail,
  28. new FunctionCall(
  29. "tl", new ExpressionSequence(new Variable("tmp" + currentTemporaryLabel), null)));
  30.  
  31. } else {
  32. tailMatch =
  33. new Match(
  34. lhs.tail != null ? lhs.tail : new List(""),
  35. new FunctionCall(
  36. "tl", new ExpressionSequence(new Variable("tmp" + currentTemporaryLabel), null)));
  37. }
  38.  
  39. this.subgraphSize = 2 + this.rhs.subgraphSize + headMatch.subgraphSize + tailMatch.subgraphSize;
  40. }
  41.  
  42. public void generateCode(Manager manager, Node parent) {
  43. manager.dumpln("\t; start " + this.getClass().getName() + "(" + subgraphSize + ")");
  44. super.generateCode(manager, parent);
  45.  
  46. rhs.generateCode(manager, this);
  47. label = rhs.label;
  48. manager.dumpCodeLabel();
  49.  
  50. headMatch.generateCode(manager, this);
  51. manager.dumpCodeLabel();
  52.  
  53. tailMatch.generateCode(manager, this);
  54. }
  55.  
  56. public long destruct(Manager manager, Node caller) {
  57. return destructDependencies(manager, caller);
  58. }
  59.  
  60. public long destructDependencies(Manager manager, Node caller) {
  61.  
  62. long maxParentDep = 0;
  63. if (caller != parent) {
  64. maxParentDep = parent.destruct(manager, this);
  65. }
  66.  
  67. if (rhs != caller) {
  68. if (rhs.label >= maxParentDep) {
  69. maxParentDep = Math.max(rhs.destruct(manager, this), maxParentDep);
  70. }
  71. if (headMatch != caller) {
  72. if (headMatch.label > maxParentDep) {
  73. maxParentDep = Math.max(headMatch.destruct(manager, this), maxParentDep);
  74. }
  75. if (tailMatch != caller && tailMatch.label > maxParentDep) {
  76. maxParentDep = Math.max(tailMatch.destruct(manager, this), maxParentDep);
  77. } else {
  78. }
  79. }
  80. }
  81. return maxParentDep;
  82. }
  83. }

Example code

Fibonacci:

  1. fib(0) -> 0;
  2. fib(1) -> 1;
  3. fib(N) -> Res = fib(N-1) + fib(N-2).

Pattern Matching:

  1. patternMatching() ->
  2. Five = 5,
  3. io:format("Five: ~w~n", [Five]),
  4. % outputs: "Five: 5\n"
  5. [H | T] = [1, 2, 3, 4],
  6. io:format("H: ~w T: ~w~n", [H, T]),
  7. % outputs: "H: 1 T: [2,3,4]\n"
  8. ComplexList = [1, 2, [3, 4, 5]],
  9. [First, Second, [HeadOfThird | TailOfThird]] = ComplexList,
  10. io:format("Destructured ComplexList -> First: ~w Second: ~w HeadOfThird: ~w TailOfThird: ~w~n", [First, Second, HeadOfThird, TailOfThird]).
  11. % outputs: "Destructured ComplexList -> First: 1 Second: 2 HeadOfThird: 3 TailOfThird: [4,5]\n"

Usage guide

Code written to ./test.erl will be the target of the compiler. To compile and run the code run make.

Compiler repository


If you found any error, or if you want to partecipate to the editing of this wiki, please contact: admin [at] skenz.it

You can reuse, distribute or modify the content of this page, but you must cite in any document (or webpage) this url: https://www.skenz.it/compilers/erlang_to_llvm
/web/htdocs/www.skenz.it/home/data/pages/compilers/erlang_to_llvm.txt · Last modified: 2021/03/03 13:06 by enrico

Privacy Policy