INTRODUCTION TO COMPILER BACKEND DESIGN
The compiler backend transforms the Abstract Syntax Tree produced by the parser into executable machine code. This phase encompasses semantic analysis, type checking, symbol table management, and code generation. For PyGo, we will use LLVM as our code generation target, which provides excellent optimization capabilities and cross-platform support.
The backend must perform several critical tasks including variable and function scope resolution, static type checking, memory management, and translation of high-level PyGo constructs into LLVM Intermediate Representation. The LLVM IR serves as a platform-independent assembly language that can be optimized and compiled to native machine code.
Semantic analysis ensures that PyGo programs are not only syntactically correct but also semantically meaningful. This includes verifying that variables are declared before use, function calls match function signatures, type conversions are valid, and control flow structures are properly formed.
LLVM INTEGRATION SETUP
LLVM provides Java bindings through the LLVM-J library, which allows direct manipulation of LLVM IR from Java code. The integration requires setting up LLVM context, modules, and builders that manage the code generation process.
import org.llvm.binding.*;
import org.llvm.binding.LLVMLibrary.*;
import java.util.*;
public class LLVMContext {
private SWIGTYPE_p_LLVMOpaqueContext context;
private SWIGTYPE_p_LLVMOpaqueModule module;
private SWIGTYPE_p_LLVMOpaqueBuilder builder;
private Map<String, SWIGTYPE_p_LLVMOpaqueValue> namedValues;
public LLVMContext(String moduleName) {
// Initialize LLVM
LLVM.LLVMInitializeCore(LLVM.LLVMGetGlobalPassRegistry());
LLVM.LLVMInitializeNativeTarget();
LLVM.LLVMInitializeNativeAsmPrinter();
// Create LLVM context and module
this.context = LLVM.LLVMContextCreate();
this.module = LLVM.LLVMModuleCreateWithNameInContext(moduleName, context);
this.builder = LLVM.LLVMCreateBuilderInContext(context);
this.namedValues = new HashMap<>();
}
public SWIGTYPE_p_LLVMOpaqueContext getContext() { return context; }
public SWIGTYPE_p_LLVMOpaqueModule getModule() { return module; }
public SWIGTYPE_p_LLVMOpaqueBuilder getBuilder() { return builder; }
public void addNamedValue(String name, SWIGTYPE_p_LLVMOpaqueValue value) {
namedValues.put(name, value);
}
public SWIGTYPE_p_LLVMOpaqueValue getNamedValue(String name) {
return namedValues.get(name);
}
public void dispose() {
LLVM.LLVMDisposeBuilder(builder);
LLVM.LLVMDisposeModule(module);
LLVM.LLVMContextDispose(context);
}
}
The LLVM context manages the global state for code generation including type definitions, function declarations, and optimization settings. The module represents a compilation unit that contains all generated functions and global variables.
SYMBOL TABLE IMPLEMENTATION
Symbol tables track variable and function declarations throughout different scopes in PyGo programs. The symbol table implementation must handle nested scopes, type information, and memory locations for efficient code generation.
public class Symbol {
private String name;
private PyGoType type;
private SWIGTYPE_p_LLVMOpaqueValue llvmValue;
private boolean isFunction;
private int scopeLevel;
public Symbol(String name, PyGoType type, SWIGTYPE_p_LLVMOpaqueValue llvmValue,
boolean isFunction, int scopeLevel) {
this.name = name;
this.type = type;
this.llvmValue = llvmValue;
this.isFunction = isFunction;
this.scopeLevel = scopeLevel;
}
public String getName() { return name; }
public PyGoType getType() { return type; }
public SWIGTYPE_p_LLVMOpaqueValue getLLVMValue() { return llvmValue; }
public boolean isFunction() { return isFunction; }
public int getScopeLevel() { return scopeLevel; }
}
public class SymbolTable {
private List<Map<String, Symbol>> scopes;
private int currentScopeLevel;
public SymbolTable() {
this.scopes = new ArrayList<>();
this.currentScopeLevel = -1;
enterScope(); // Global scope
}
public void enterScope() {
scopes.add(new HashMap<>());
currentScopeLevel++;
}
public void exitScope() {
if (currentScopeLevel > 0) {
scopes.remove(currentScopeLevel);
currentScopeLevel--;
}
}
public void declareSymbol(String name, PyGoType type,
SWIGTYPE_p_LLVMOpaqueValue llvmValue, boolean isFunction) {
if (scopes.get(currentScopeLevel).containsKey(name)) {
throw new SemanticException("Symbol '" + name + "' already declared in current scope");
}
Symbol symbol = new Symbol(name, type, llvmValue, isFunction, currentScopeLevel);
scopes.get(currentScopeLevel).put(name, symbol);
}
public Symbol lookupSymbol(String name) {
for (int i = currentScopeLevel; i >= 0; i--) {
Symbol symbol = scopes.get(i).get(name);
if (symbol != null) {
return symbol;
}
}
return null;
}
public boolean isSymbolDeclared(String name) {
return lookupSymbol(name) != null;
}
public int getCurrentScopeLevel() {
return currentScopeLevel;
}
}
The symbol table uses a stack of hash maps to represent nested scopes. Symbol lookup searches from the current scope outward to implement proper variable shadowing and scope resolution according to PyGo semantics.
TYPE SYSTEM IMPLEMENTATION
PyGo's type system requires a comprehensive representation that supports type checking, type conversion, and LLVM type mapping. The type system must handle primitive types and provide extensibility for future language enhancements.
public abstract class PyGoType {
protected String name;
public PyGoType(String name) {
this.name = name;
}
public String getName() { return name; }
public abstract SWIGTYPE_p_LLVMOpaqueType getLLVMType(LLVMContext context);
public abstract boolean isCompatibleWith(PyGoType other);
public abstract int getSize();
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (obj == null || getClass() != obj.getClass()) return false;
PyGoType other = (PyGoType) obj;
return name.equals(other.name);
}
@Override
public int hashCode() {
return name.hashCode();
}
}
public class IntType extends PyGoType {
public IntType() {
super("int");
}
@Override
public SWIGTYPE_p_LLVMOpaqueType getLLVMType(LLVMContext context) {
return LLVM.LLVMInt32TypeInContext(context.getContext());
}
@Override
public boolean isCompatibleWith(PyGoType other) {
return other instanceof IntType;
}
@Override
public int getSize() {
return 4; // 32-bit integer
}
}
public class FloatType extends PyGoType {
public FloatType() {
super("float");
}
@Override
public SWIGTYPE_p_LLVMOpaqueType getLLVMType(LLVMContext context) {
return LLVM.LLVMDoubleTypeInContext(context.getContext());
}
@Override
public boolean isCompatibleWith(PyGoType other) {
return other instanceof FloatType || other instanceof IntType;
}
@Override
public int getSize() {
return 8; // 64-bit double
}
}
public class StringType extends PyGoType {
public StringType() {
super("string");
}
@Override
public SWIGTYPE_p_LLVMOpaqueType getLLVMType(LLVMContext context) {
return LLVM.LLVMPointerType(LLVM.LLVMInt8TypeInContext(context.getContext()), 0);
}
@Override
public boolean isCompatibleWith(PyGoType other) {
return other instanceof StringType;
}
@Override
public int getSize() {
return 8; // Pointer size
}
}
public class BoolType extends PyGoType {
public BoolType() {
super("bool");
}
@Override
public SWIGTYPE_p_LLVMOpaqueType getLLVMType(LLVMContext context) {
return LLVM.LLVMInt1TypeInContext(context.getContext());
}
@Override
public boolean isCompatibleWith(PyGoType other) {
return other instanceof BoolType;
}
@Override
public int getSize() {
return 1; // Boolean
}
}
public class VoidType extends PyGoType {
public VoidType() {
super("void");
}
@Override
public SWIGTYPE_p_LLVMOpaqueType getLLVMType(LLVMContext context) {
return LLVM.LLVMVoidTypeInContext(context.getContext());
}
@Override
public boolean isCompatibleWith(PyGoType other) {
return other instanceof VoidType;
}
@Override
public int getSize() {
return 0;
}
}
SEMANTIC ANALYZER IMPLEMENTATION
The semantic analyzer performs type checking, scope resolution, and semantic validation by traversing the AST and building symbol tables. This phase ensures that PyGo programs are semantically correct before code generation.
public class SemanticAnalyzer implements ASTVisitor {
private SymbolTable symbolTable;
private List<SemanticError> errors;
private PyGoType currentFunctionReturnType;
public SemanticAnalyzer() {
this.symbolTable = new SymbolTable();
this.errors = new ArrayList<>();
this.currentFunctionReturnType = null;
}
public AnalysisResult analyze(ProgramNode program) {
errors.clear();
try {
program.accept(this);
} catch (Exception e) {
errors.add(new SemanticError(0, 0, "Internal semantic analysis error: " + e.getMessage()));
}
return new AnalysisResult(symbolTable, errors);
}
@Override
public void visitProgram(ProgramNode node) {
// First pass: declare all functions
for (DeclarationNode declaration : node.getDeclarations()) {
if (declaration instanceof FunctionDeclarationNode) {
declareFunctionSignature((FunctionDeclarationNode) declaration);
}
}
// Second pass: analyze function bodies and global variables
for (DeclarationNode declaration : node.getDeclarations()) {
declaration.accept(this);
}
}
private void declareFunctionSignature(FunctionDeclarationNode node) {
String functionName = node.getIdentifier();
if (symbolTable.isSymbolDeclared(functionName)) {
addError(node, "Function '" + functionName + "' already declared");
return;
}
// Build function type
List<PyGoType> paramTypes = new ArrayList<>();
for (ParameterNode param : node.getParameters()) {
PyGoType paramType = convertTypeNode(param.getType());
paramTypes.add(paramType);
}
PyGoType returnType = node.getReturnType() != null ?
convertTypeNode(node.getReturnType()) : new VoidType();
FunctionType funcType = new FunctionType(returnType, paramTypes);
// Declare function in symbol table (LLVM value will be set during code generation)
symbolTable.declareSymbol(functionName, funcType, null, true);
}
@Override
public void visitFunctionDeclaration(FunctionDeclarationNode node) {
String functionName = node.getIdentifier();
Symbol functionSymbol = symbolTable.lookupSymbol(functionName);
if (functionSymbol == null) {
addError(node, "Internal error: function not pre-declared");
return;
}
FunctionType funcType = (FunctionType) functionSymbol.getType();
currentFunctionReturnType = funcType.getReturnType();
// Enter function scope
symbolTable.enterScope();
// Declare parameters in function scope
List<ParameterNode> parameters = node.getParameters();
for (int i = 0; i < parameters.size(); i++) {
ParameterNode param = parameters.get(i);
String paramName = param.getIdentifier();
PyGoType paramType = convertTypeNode(param.getType());
if (symbolTable.isSymbolDeclared(paramName)) {
addError(param, "Parameter '" + paramName + "' already declared");
} else {
symbolTable.declareSymbol(paramName, paramType, null, false);
}
}
// Analyze function body
node.getBody().accept(this);
// Check return statements
if (!funcType.getReturnType().equals(new VoidType())) {
if (!hasReturnStatement(node.getBody())) {
addError(node, "Function '" + functionName + "' must return a value");
}
}
// Exit function scope
symbolTable.exitScope();
currentFunctionReturnType = null;
}
@Override
public void visitVariableDeclaration(VariableDeclarationNode node) {
String varName = node.getIdentifier();
PyGoType varType = convertTypeNode(node.getType());
if (symbolTable.isSymbolDeclared(varName)) {
addError(node, "Variable '" + varName + "' already declared in current scope");
return;
}
// Check initializer type compatibility if present
if (node.getInitializer() != null) {
PyGoType initType = analyzeExpression(node.getInitializer());
if (!varType.isCompatibleWith(initType)) {
addError(node, "Cannot initialize variable of type '" + varType.getName() +
"' with value of type '" + initType.getName() + "'");
}
}
symbolTable.declareSymbol(varName, varType, null, false);
}
private PyGoType analyzeExpression(ExpressionNode node) {
if (node instanceof BinaryExpressionNode) {
return analyzeBinaryExpression((BinaryExpressionNode) node);
} else if (node instanceof UnaryExpressionNode) {
return analyzeUnaryExpression((UnaryExpressionNode) node);
} else if (node instanceof LiteralExpressionNode) {
return analyzeLiteralExpression((LiteralExpressionNode) node);
} else if (node instanceof IdentifierExpressionNode) {
return analyzeIdentifierExpression((IdentifierExpressionNode) node);
} else if (node instanceof FunctionCallExpressionNode) {
return analyzeFunctionCallExpression((FunctionCallExpressionNode) node);
}
addError(node, "Unknown expression type");
return new VoidType();
}
private PyGoType analyzeBinaryExpression(BinaryExpressionNode node) {
PyGoType leftType = analyzeExpression(node.getLeft());
PyGoType rightType = analyzeExpression(node.getRight());
String operator = node.getOperator();
// Arithmetic operators
if (operator.equals("+") || operator.equals("-") ||
operator.equals("*") || operator.equals("/") || operator.equals("%")) {
if (leftType instanceof IntType && rightType instanceof IntType) {
return new IntType();
} else if ((leftType instanceof FloatType || leftType instanceof IntType) &&
(rightType instanceof FloatType || rightType instanceof IntType)) {
return new FloatType();
} else {
addError(node, "Arithmetic operator '" + operator +
"' not applicable to types '" + leftType.getName() +
"' and '" + rightType.getName() + "'");
return new VoidType();
}
}
// Comparison operators
if (operator.equals("==") || operator.equals("!=") ||
operator.equals("<") || operator.equals("<=") ||
operator.equals(">") || operator.equals(">=")) {
if (leftType.isCompatibleWith(rightType) || rightType.isCompatibleWith(leftType)) {
return new BoolType();
} else {
addError(node, "Comparison operator '" + operator +
"' not applicable to types '" + leftType.getName() +
"' and '" + rightType.getName() + "'");
return new VoidType();
}
}
// Logical operators
if (operator.equals("and") || operator.equals("or")) {
if (leftType instanceof BoolType && rightType instanceof BoolType) {
return new BoolType();
} else {
addError(node, "Logical operator '" + operator +
"' requires boolean operands");
return new VoidType();
}
}
addError(node, "Unknown binary operator: " + operator);
return new VoidType();
}
private void addError(ASTNode node, String message) {
errors.add(new SemanticError(node.getLineNumber(), node.getColumnNumber(), message));
}
private PyGoType convertTypeNode(TypeNode typeNode) {
switch (typeNode.getTypeName()) {
case "int": return new IntType();
case "float": return new FloatType();
case "string": return new StringType();
case "bool": return new BoolType();
default:
addError(typeNode, "Unknown type: " + typeNode.getTypeName());
return new VoidType();
}
}
}
CODE GENERATOR IMPLEMENTATION
The code generator traverses the semantically validated AST and produces LLVM IR code. This phase handles memory allocation, function calls, control flow, and expression evaluation while leveraging LLVM's optimization capabilities.
public class CodeGenerator implements ASTVisitor {
private LLVMContext llvmContext;
private SymbolTable symbolTable;
private List<CodeGenError> errors;
private SWIGTYPE_p_LLVMOpaqueValue currentFunction;
public CodeGenerator() {
this.errors = new ArrayList<>();
}
public CodeGenResult generate(ProgramNode program, SymbolTable symbolTable) {
this.llvmContext = new LLVMContext("PyGoModule");
this.symbolTable = symbolTable;
this.errors.clear();
try {
// Generate built-in function declarations
generateBuiltinFunctions();
// Generate code for all declarations
program.accept(this);
// Verify the module
if (LLVM.LLVMVerifyModule(llvmContext.getModule(),
LLVMLibrary.LLVMVerifierFailureAction.LLVMPrintMessageAction,
null) != 0) {
errors.add(new CodeGenError(0, 0, "LLVM module verification failed"));
}
} catch (Exception e) {
errors.add(new CodeGenError(0, 0, "Code generation error: " + e.getMessage()));
}
return new CodeGenResult(llvmContext, errors);
}
private void generateBuiltinFunctions() {
// Generate printf declaration for print function
SWIGTYPE_p_LLVMOpaqueType[] printfParamTypes = {
LLVM.LLVMPointerType(LLVM.LLVMInt8TypeInContext(llvmContext.getContext()), 0)
};
SWIGTYPE_p_LLVMOpaqueType printfType = LLVM.LLVMFunctionType(
LLVM.LLVMInt32TypeInContext(llvmContext.getContext()),
printfParamTypes, 1, 1
);
SWIGTYPE_p_LLVMOpaqueValue printfFunc = LLVM.LLVMAddFunction(
llvmContext.getModule(), "printf", printfType
);
llvmContext.addNamedValue("printf", printfFunc);
}
@Override
public void visitProgram(ProgramNode node) {
for (DeclarationNode declaration : node.getDeclarations()) {
declaration.accept(this);
}
}
@Override
public void visitFunctionDeclaration(FunctionDeclarationNode node) {
String functionName = node.getIdentifier();
Symbol functionSymbol = symbolTable.lookupSymbol(functionName);
if (functionSymbol == null) {
addError(node, "Function symbol not found: " + functionName);
return;
}
FunctionType funcType = (FunctionType) functionSymbol.getType();
// Create LLVM function type
SWIGTYPE_p_LLVMOpaqueType[] paramTypes = new SWIGTYPE_p_LLVMOpaqueType[funcType.getParameterTypes().size()];
for (int i = 0; i < funcType.getParameterTypes().size(); i++) {
paramTypes[i] = funcType.getParameterTypes().get(i).getLLVMType(llvmContext);
}
SWIGTYPE_p_LLVMOpaqueType llvmFuncType = LLVM.LLVMFunctionType(
funcType.getReturnType().getLLVMType(llvmContext),
paramTypes, paramTypes.length, 0
);
// Create LLVM function
SWIGTYPE_p_LLVMOpaqueValue llvmFunction = LLVM.LLVMAddFunction(
llvmContext.getModule(), functionName, llvmFuncType
);
// Update symbol table with LLVM value
symbolTable.declareSymbol(functionName, funcType, llvmFunction, true);
currentFunction = llvmFunction;
// Create entry basic block
SWIGTYPE_p_LLVMOpaqueBasicBlock entryBlock = LLVM.LLVMAppendBasicBlockInContext(
llvmContext.getContext(), llvmFunction, "entry"
);
LLVM.LLVMPositionBuilderAtEnd(llvmContext.getBuilder(), entryBlock);
// Enter function scope and allocate parameters
symbolTable.enterScope();
List<ParameterNode> parameters = node.getParameters();
for (int i = 0; i < parameters.size(); i++) {
ParameterNode param = parameters.get(i);
String paramName = param.getIdentifier();
PyGoType paramType = convertTypeNode(param.getType());
// Get parameter value from function
SWIGTYPE_p_LLVMOpaqueValue paramValue = LLVM.LLVMGetParam(llvmFunction, i);
LLVM.LLVMSetValueName(paramValue, paramName);
// Allocate stack space for parameter
SWIGTYPE_p_LLVMOpaqueValue alloca = LLVM.LLVMBuildAlloca(
llvmContext.getBuilder(), paramType.getLLVMType(llvmContext), paramName
);
// Store parameter value to stack
LLVM.LLVMBuildStore(llvmContext.getBuilder(), paramValue, alloca);
// Update symbol table
symbolTable.declareSymbol(paramName, paramType, alloca, false);
}
// Generate function body
node.getBody().accept(this);
// Add return instruction if missing
if (!funcType.getReturnType().equals(new VoidType())) {
// Check if last instruction is already a return
SWIGTYPE_p_LLVMOpaqueBasicBlock currentBlock = LLVM.LLVMGetInsertBlock(llvmContext.getBuilder());
SWIGTYPE_p_LLVMOpaqueValue lastInst = LLVM.LLVMGetLastInstruction(currentBlock);
if (lastInst == null || LLVM.LLVMGetInstructionOpcode(lastInst) != LLVMLibrary.LLVMOpcode.LLVMRet) {
// Add default return value
SWIGTYPE_p_LLVMOpaqueValue defaultValue = getDefaultValue(funcType.getReturnType());
LLVM.LLVMBuildRet(llvmContext.getBuilder(), defaultValue);
}
} else {
// Void function - add return void if missing
SWIGTYPE_p_LLVMOpaqueBasicBlock currentBlock = LLVM.LLVMGetInsertBlock(llvmContext.getBuilder());
SWIGTYPE_p_LLVMOpaqueValue lastInst = LLVM.LLVMGetLastInstruction(currentBlock);
if (lastInst == null || LLVM.LLVMGetInstructionOpcode(lastInst) != LLVMLibrary.LLVMOpcode.LLVMRet) {
LLVM.LLVMBuildRetVoid(llvmContext.getBuilder());
}
}
symbolTable.exitScope();
currentFunction = null;
}
@Override
public void visitVariableDeclaration(VariableDeclarationNode node) {
String varName = node.getIdentifier();
PyGoType varType = convertTypeNode(node.getType());
// Allocate stack space for variable
SWIGTYPE_p_LLVMOpaqueValue alloca = LLVM.LLVMBuildAlloca(
llvmContext.getBuilder(), varType.getLLVMType(llvmContext), varName
);
// Initialize with default value or provided initializer
SWIGTYPE_p_LLVMOpaqueValue initValue;
if (node.getInitializer() != null) {
initValue = generateExpression(node.getInitializer());
} else {
initValue = getDefaultValue(varType);
}
LLVM.LLVMBuildStore(llvmContext.getBuilder(), initValue, alloca);
// Update symbol table
symbolTable.declareSymbol(varName, varType, alloca, false);
}
private SWIGTYPE_p_LLVMOpaqueValue generateExpression(ExpressionNode node) {
if (node instanceof BinaryExpressionNode) {
return generateBinaryExpression((BinaryExpressionNode) node);
} else if (node instanceof UnaryExpressionNode) {
return generateUnaryExpression((UnaryExpressionNode) node);
} else if (node instanceof LiteralExpressionNode) {
return generateLiteralExpression((LiteralExpressionNode) node);
} else if (node instanceof IdentifierExpressionNode) {
return generateIdentifierExpression((IdentifierExpressionNode) node);
} else if (node instanceof FunctionCallExpressionNode) {
return generateFunctionCallExpression((FunctionCallExpressionNode) node);
}
addError(node, "Unknown expression type for code generation");
return getDefaultValue(new IntType());
}
private SWIGTYPE_p_LLVMOpaqueValue generateBinaryExpression(BinaryExpressionNode node) {
SWIGTYPE_p_LLVMOpaqueValue left = generateExpression(node.getLeft());
SWIGTYPE_p_LLVMOpaqueValue right = generateExpression(node.getRight());
String operator = node.getOperator();
switch (operator) {
case "+":
return LLVM.LLVMBuildAdd(llvmContext.getBuilder(), left, right, "addtmp");
case "-":
return LLVM.LLVMBuildSub(llvmContext.getBuilder(), left, right, "subtmp");
case "*":
return LLVM.LLVMBuildMul(llvmContext.getBuilder(), left, right, "multmp");
case "/":
return LLVM.LLVMBuildSDiv(llvmContext.getBuilder(), left, right, "divtmp");
case "%":
return LLVM.LLVMBuildSRem(llvmContext.getBuilder(), left, right, "modtmp");
case "==":
return LLVM.LLVMBuildICmp(llvmContext.getBuilder(),
LLVMLibrary.LLVMIntPredicate.LLVMIntEQ, left, right, "eqtmp");
case "!=":
return LLVM.LLVMBuildICmp(llvmContext.getBuilder(),
LLVMLibrary.LLVMIntPredicate.LLVMIntNE, left, right, "netmp");
case "<":
return LLVM.LLVMBuildICmp(llvmContext.getBuilder(),
LLVMLibrary.LLVMIntPredicate.LLVMIntSLT, left, right, "lttmp");
case "<=":
return LLVM.LLVMBuildICmp(llvmContext.getBuilder(),
LLVMLibrary.LLVMIntPredicate.LLVMIntSLE, left, right, "letmp");
case ">":
return LLVM.LLVMBuildICmp(llvmContext.getBuilder(),
LLVMLibrary.LLVMIntPredicate.LLVMIntSGT, left, right, "gttmp");
case ">=":
return LLVM.LLVMBuildICmp(llvmContext.getBuilder(),
LLVMLibrary.LLVMIntPredicate.LLVMIntSGE, left, right, "getmp");
case "and":
return LLVM.LLVMBuildAnd(llvmContext.getBuilder(), left, right, "andtmp");
case "or":
return LLVM.LLVMBuildOr(llvmContext.getBuilder(), left, right, "ortmp");
default:
addError(node, "Unknown binary operator: " + operator);
return getDefaultValue(new IntType());
}
}
private SWIGTYPE_p_LLVMOpaqueValue generateLiteralExpression(LiteralExpressionNode node) {
Object value = node.getValue();
if (value instanceof Integer) {
return LLVM.LLVMConstInt(LLVM.LLVMInt32TypeInContext(llvmContext.getContext()),
(Integer) value, 0);
} else if (value instanceof Double) {
return LLVM.LLVMConstReal(LLVM.LLVMDoubleTypeInContext(llvmContext.getContext()),
(Double) value);
} else if (value instanceof String) {
return LLVM.LLVMBuildGlobalStringPtr(llvmContext.getBuilder(),
(String) value, "strtmp");
} else if (value instanceof Boolean) {
return LLVM.LLVMConstInt(LLVM.LLVMInt1TypeInContext(llvmContext.getContext()),
(Boolean) value ? 1 : 0, 0);
}
addError(node, "Unknown literal type");
return getDefaultValue(new IntType());
}
private SWIGTYPE_p_LLVMOpaqueValue getDefaultValue(PyGoType type) {
if (type instanceof IntType) {
return LLVM.LLVMConstInt(type.getLLVMType(llvmContext), 0, 0);
} else if (type instanceof FloatType) {
return LLVM.LLVMConstReal(type.getLLVMType(llvmContext), 0.0);
} else if (type instanceof BoolType) {
return LLVM.LLVMConstInt(type.getLLVMType(llvmContext), 0, 0);
} else if (type instanceof StringType) {
return LLVM.LLVMConstPointerNull(type.getLLVMType(llvmContext));
}
return null;
}
private void addError(ASTNode node, String message) {
errors.add(new CodeGenError(node.getLineNumber(), node.getColumnNumber(), message));
}
}
COMPLETE BACKEND INTEGRATION
The complete backend integrates semantic analysis and code generation into a unified compilation phase that processes the AST and produces executable LLVM IR code.
public class PyGoBackend {
private SemanticAnalyzer semanticAnalyzer;
private CodeGenerator codeGenerator;
public PyGoBackend() {
this.semanticAnalyzer = new SemanticAnalyzer();
this.codeGenerator = new CodeGenerator();
}
public CompilationResult compile(ProgramNode ast) {
List<CompilationError> allErrors = new ArrayList<>();
// Perform semantic analysis
AnalysisResult analysisResult = semanticAnalyzer.analyze(ast);
allErrors.addAll(analysisResult.getErrors());
if (!analysisResult.hasErrors()) {
// Generate code if semantic analysis succeeded
CodeGenResult codeGenResult = codeGenerator.generate(ast, analysisResult.getSymbolTable());
allErrors.addAll(codeGenResult.getErrors());
if (!codeGenResult.hasErrors()) {
return new CompilationResult(codeGenResult.getLLVMContext(), allErrors);
}
}
return new CompilationResult(null, allErrors);
}
public void writeObjectFile(LLVMContext context, String filename) {
// Initialize target machine
LLVM.LLVMInitializeAllTargetInfos();
LLVM.LLVMInitializeAllTargets();
LLVM.LLVMInitializeAllTargetMCs();
LLVM.LLVMInitializeAllAsmParsers();
LLVM.LLVMInitializeAllAsmPrinters();
String targetTriple = LLVM.LLVMGetDefaultTargetTriple();
LLVM.LLVMSetTarget(context.getModule(), targetTriple);
// Create target machine and emit object file
SWIGTYPE_p_LLVMOpaqueTargetMachine targetMachine = LLVM.LLVMCreateTargetMachine(
LLVM.LLVMGetFirstTarget(), targetTriple, "generic", "",
LLVMLibrary.LLVMCodeGenOptLevel.LLVMCodeGenLevelDefault,
LLVMLibrary.LLVMRelocMode.LLVMRelocDefault,
LLVMLibrary.LLVMCodeModel.LLVMCodeModelDefault
);
LLVM.LLVMTargetMachineEmitToFile(targetMachine, context.getModule(),
filename, LLVMLibrary.LLVMCodeGenFileType.LLVMObjectFile, null);
}
}
COMPREHENSIVE BACKEND TESTING
Testing the backend requires validating both semantic analysis and code generation across various PyGo language constructs while ensuring that generated LLVM IR is correct and executable.
public class PyGoBackendTest {
private PyGoBackend backend;
private PyGoParserWrapper parser;
public PyGoBackendTest() {
this.backend = new PyGoBackend();
this.parser = new PyGoParserWrapper();
}
public void runAllTests() {
testSimplePrograms();
testTypeChecking();
testFunctionCalls();
testControlFlow();
testSemanticErrors();
System.out.println("All backend tests completed successfully");
}
private void testSimplePrograms() {
String simpleProgram = """
func add(x: int, y: int) -> int:
{
return x + y
}
func main():
{
var result: int = add(5, 3)
print(result)
}
""";
ParseResult parseResult = parser.parse(simpleProgram);
assert parseResult.isSuccessful() : "Simple program should parse successfully";
CompilationResult compileResult = backend.compile(parseResult.getAST());
assert compileResult.isSuccessful() : "Simple program should compile successfully";
}
private void testTypeChecking() {
String typeErrorProgram = """
func test():
{
var x: int = 5
var y: string = "hello"
var z: int = x + y
}
""";
ParseResult parseResult = parser.parse(typeErrorProgram);
assert parseResult.isSuccessful() : "Program should parse successfully";
CompilationResult compileResult = backend.compile(parseResult.getAST());
assert compileResult.hasErrors() : "Type error program should produce compilation errors";
}
private void testFunctionCalls() {
String functionProgram = """
func multiply(a: int, b: int) -> int:
{
return a * b
}
func calculate():
{
var x: int = 4
var y: int = 7
var product: int = multiply(x, y)
}
""";
ParseResult parseResult = parser.parse(functionProgram);
assert parseResult.isSuccessful() : "Function program should parse successfully";
CompilationResult compileResult = backend.compile(parseResult.getAST());
assert compileResult.isSuccessful() : "Function program should compile successfully";
}
}
CONCLUSION OF ARTICLE 4
This article has demonstrated the complete implementation of the PyGo compiler backend using LLVM for code generation. The backend performs comprehensive semantic analysis including type checking, scope resolution, and symbol table management while generating efficient LLVM IR code.
The semantic analyzer ensures that PyGo programs are not only syntactically correct but also semantically meaningful. Type checking prevents runtime errors by catching type mismatches at compile time, while scope resolution ensures proper variable and function visibility.
The code generator translates the validated AST into LLVM IR, leveraging LLVM's optimization infrastructure and cross-platform code generation capabilities. The generated code handles function calls, variable allocation, expression evaluation, and control flow according to PyGo semantics.
The integration of semantic analysis and code generation provides a robust foundation for producing correct and efficient executable code from PyGo source programs. The comprehensive error handling ensures that programmers receive detailed feedback about both semantic and code generation problems.
In Article 5, we will implement optimization passes that improve the performance of the generated LLVM IR code. The optimizer will demonstrate various optimization techniques including constant folding, dead code elimination, and function inlining while maintaining program correctness.
No comments:
Post a Comment