Added runtime check for array index and division

5 files changed, 104 insertions, 13 deletions

diff --git a/lib/CodeGen/ArrayHandler.cc b/lib/CodeGen/ArrayHandler.cc
index 470cffa..499fd2d 100644
--- a/lib/CodeGen/ArrayHandler.cc
+++ b/lib/CodeGen/ArrayHandler.cc
@@ -8,8 +8,8 @@
 using namespace llvm;
 using namespace cps;
 
-ArrayHandler::ArrayHandler(LLVMContext &C, IRBuilder<> &B, Module &M, std::map<std::string, AllocaInst*> &NV)
-    : TheContext(&C), Builder(&B), TheModule(&M), NamedValues(&NV) {
+ArrayHandler::ArrayHandler(LLVMContext &C, IRBuilder<> &B, Module &M, std::map<std::string, AllocaInst*> &NV, RuntimeCheck &RC)
+    : TheContext(&C), Builder(&B), TheModule(&M), NamedValues(&NV), RuntimeChecker(RC) {
     setupExternalFunctions();
 }
 
@@ -115,8 +115,13 @@ Value* ArrayHandler::emitArrayAccess(ArrayAccessExprAST *Expr, CodeGen &CG) {
     }
 
     std::vector<Value*> Indices;
-    for (const auto &IdxExpr : Expr->getIndices()) {
-        Indices.push_back(CG.emitExpr(IdxExpr.get()));
+    for (size_t i = 0; i < Expr->getIndices().size(); ++i) {
+        Value *Idx = CG.emitExpr(Expr->getIndices()[i].get());
+        Indices.push_back(Idx);
+
+        Value *Lower = Meta.LowerBounds[i];
+        Value *Upper = Meta.UpperBounds[i];
+        RuntimeChecker.emitIndexCheck(Idx, Lower, Upper, Expr->getLine());
     }
     
     Value *Offset = computeFlatIndex(Name, Indices);
@@ -137,8 +142,14 @@ void ArrayHandler::emitArrayAssign(ArrayAssignStmtAST *Stmt, CodeGen &CG) {
     }
     
     std::vector<Value*> Indices;
-    for (const auto &IdxExpr : Stmt->getIndices()) {
-        Indices.push_back(CG.emitExpr(IdxExpr.get()));
+    for (size_t i = 0; i < Stmt->getIndices().size(); ++i) {
+        Value *Idx = CG.emitExpr(Stmt->getIndices()[i].get());
+        Indices.push_back(Idx);
+
+        const auto &Meta = ArrayTable[Name];
+        Value *Lower = Meta.LowerBounds[i];
+        Value *Upper = Meta.UpperBounds[i];
+        RuntimeChecker.emitIndexCheck(Idx, Lower, Upper, Stmt->getLine());
     }
     
     Value *Val = CG.emitExpr(Stmt->getExpr());
diff --git a/lib/CodeGen/CodeGen.cc b/lib/CodeGen/CodeGen.cc
index 57d76eb..e2c959e 100644
--- a/lib/CodeGen/CodeGen.cc
+++ b/lib/CodeGen/CodeGen.cc
@@ -13,7 +13,9 @@ CodeGen::CodeGen() {
     TheModule = std::make_unique<Module>("cps_module", *TheContext);
     Builder = std::make_unique<IRBuilder<>>(*TheContext);
     
-    Arrays = std::make_unique<ArrayHandler>(*TheContext, *Builder, *TheModule, NamedValues);
+    RuntimeChecker = std::make_unique<RuntimeCheck>(*TheModule, *TheContext, *Builder);
+    
+    Arrays = std::make_unique<ArrayHandler>(*TheContext, *Builder, *TheModule, NamedValues, *RuntimeChecker);
     
     SetupExternalFunctions();
 }
@@ -89,7 +91,9 @@ Value *CodeGen::emitExpr(ExprAST *Expr) {
         case '+': return Builder->CreateAdd(L, R, "addtmp");
         case '-': return Builder->CreateSub(L, R, "subtmp");
         case '*': return Builder->CreateMul(L, R, "multmp");
-        case '/': return Builder->CreateSDiv(L, R, "divtmp");
+        case '/': 
+            RuntimeChecker->emitDivZeroCheck(R, Bin->getLine());
+            return Builder->CreateSDiv(L, R, "divtmp");
         case tok_eq: return Builder->CreateICmpEQ(L, R, "eqtmp");
         case tok_ne: return Builder->CreateICmpNE(L, R, "netmp");
         case '<':    return Builder->CreateICmpSLT(L, R, "slttmp");
diff --git a/lib/CodeGen/RuntimeCheck.cc b/lib/CodeGen/RuntimeCheck.cc
new file mode 100644
index 0000000..cab50d5
--- /dev/null
+++ b/lib/CodeGen/RuntimeCheck.cc
@@ -0,0 +1,60 @@
+#include "cps/RuntimeCheck.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Type.h"
+#include "llvm/IR/Constants.h"
+
+using namespace llvm;
+using namespace cps;
+
+RuntimeCheck::RuntimeCheck(Module &M, LLVMContext &C, IRBuilder<> &B)
+    : TheModule(M), TheContext(C), Builder(B) {
+    setupExternalFunctions();
+}
+
+void RuntimeCheck::setupExternalFunctions() {
+    std::vector<Type*> PrintfArgs;
+    PrintfArgs.push_back(PointerType::getUnqual(TheContext));
+    FunctionType *PrintfType = FunctionType::get(Type::getInt32Ty(TheContext), PrintfArgs, true);
+    PrintfFunc = TheModule.getOrInsertFunction("printf", PrintfType);
+
+    std::vector<Type*> ExitArgs;
+    ExitArgs.push_back(Type::getInt32Ty(TheContext));
+    FunctionType *ExitType = FunctionType::get(Type::getVoidTy(TheContext), ExitArgs, false);
+    ExitFunc = TheModule.getOrInsertFunction("exit", ExitType);
+
+    DivZeroMsg = Builder.CreateGlobalStringPtr("[Fatal] line %d: Division by zero\n", "err_div_zero", 0, &TheModule);
+    OutOfBoundsMsg = Builder.CreateGlobalStringPtr("[Fatal] line %d: Array index out of bounds\n", "err_bounds", 0, &TheModule);
+}
+
+void RuntimeCheck::emitErrorAndExit(Value *Condition, Value *Msg, int Line) {
+    Function *TheFunction = Builder.GetInsertBlock()->getParent();
+    
+    BasicBlock *FailBB = BasicBlock::Create(TheContext, "check_fail", TheFunction);
+    BasicBlock *ContBB = BasicBlock::Create(TheContext, "check_cont", TheFunction);
+
+    Builder.CreateCondBr(Condition, FailBB, ContBB);
+
+    Builder.SetInsertPoint(FailBB);
+    std::vector<Value*> PrintArgs;
+    PrintArgs.push_back(Msg);
+    PrintArgs.push_back(ConstantInt::get(TheContext, APInt(32, Line)));
+    Builder.CreateCall(PrintfFunc, PrintArgs);
+
+    Builder.CreateCall(ExitFunc, ConstantInt::get(TheContext, APInt(32, 1)));
+    Builder.CreateUnreachable();
+
+    Builder.SetInsertPoint(ContBB);
+}
+
+void RuntimeCheck::emitDivZeroCheck(Value *Divisor, int Line) {
+    Value *IsZero = Builder.CreateICmpEQ(Divisor, ConstantInt::get(TheContext, APInt(32, 0)), "is_zero");
+    emitErrorAndExit(IsZero, DivZeroMsg, Line);
+}
+
+void RuntimeCheck::emitIndexCheck(Value *Index, Value *Lower, Value *Upper, int Line) {
+    Value *TooLow = Builder.CreateICmpSLT(Index, Lower, "too_low");
+    Value *TooHigh = Builder.CreateICmpSGT(Index, Upper, "too_high");
+    Value *OutOfBounds = Builder.CreateOr(TooLow, TooHigh, "out_of_bounds");
+    
+    emitErrorAndExit(OutOfBounds, OutOfBoundsMsg, Line);
+}
diff --git a/lib/Lexer/Lexer.cc b/lib/Lexer/Lexer.cc
index fdaa3a5..780c79a 100644
--- a/lib/Lexer/Lexer.cc
+++ b/lib/Lexer/Lexer.cc
@@ -9,8 +9,10 @@ using namespace cps;
 int Lexer::gettok() {
     static int LastChar = ' ';
 
-    while (isspace(LastChar))
+    while (isspace(LastChar)) {
+        if (LastChar == '\n') CurrentLine++;
         LastChar = getchar();
+    }
 
     if (isalpha(LastChar)) {
         IdentifierStr = LastChar;
diff --git a/lib/Parser/Parser.cc b/lib/Parser/Parser.cc
index a85b151..b9396ce 100644
--- a/lib/Parser/Parser.cc
+++ b/lib/Parser/Parser.cc
@@ -38,6 +38,7 @@ std::unique_ptr<ExprAST> Parser::ParseNumberExpr() {
 
 std::unique_ptr<ExprAST> Parser::ParseIdentifierExpr() {
     std::string IdName = Lex.IdentifierStr;
+    int Line = Lex.getLine();
     getNextToken();
     
     if (CurTok == '[') {
@@ -60,7 +61,7 @@ std::unique_ptr<ExprAST> Parser::ParseIdentifierExpr() {
             return nullptr;
         }
         getNextToken(); 
-        return std::make_unique<ArrayAccessExprAST>(IdName, std::move(Indices));
+        return std::make_unique<ArrayAccessExprAST>(IdName, std::move(Indices), Line);
     }
     
     return std::make_unique<VariableExprAST>(IdName);
@@ -84,7 +85,8 @@ std::unique_ptr<ExprAST> Parser::ParsePrimary() {
     case tok_number:     return ParseNumberExpr();
     case '(':            return ParseParenExpr();
     default:
-        fprintf(stderr, "Error: unknown token when expecting an expression\n");
+        fprintf(stderr, "Error: unknown token '%c' (%d) at line %d when expecting an expression\n", 
+                (char)CurTok, CurTok, Lex.getLine());
         return nullptr;
     }
 }
@@ -95,6 +97,7 @@ std::unique_ptr<ExprAST> Parser::ParseBinOpRHS(int ExprPrec, std::unique_ptr<Exp
         if (TokPrec < ExprPrec) return LHS;
 
         int BinOp = CurTok;
+        int Line = Lex.getLine();
         getNextToken();
 
         auto RHS = ParsePrimary();
@@ -106,7 +109,7 @@ std::unique_ptr<ExprAST> Parser::ParseBinOpRHS(int ExprPrec, std::unique_ptr<Exp
             if (!RHS) return nullptr;
         }
 
-        LHS = std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS));
+        LHS = std::make_unique<BinaryExprAST>(BinOp, std::move(LHS), std::move(RHS), Line);
     }
 }
 
@@ -209,6 +212,7 @@ std::unique_ptr<StmtAST> Parser::ParseIfStmt() {
     while (CurTok != tok_else && CurTok != tok_endif && CurTok != tok_eof) {
         auto Stmt = ParseStatement();
         if (Stmt) ThenStmts.push_back(std::move(Stmt));
+        else if (CurTok != tok_eof && CurTok != tok_else && CurTok != tok_endif) getNextToken();
     }
 
     std::vector<std::unique_ptr<StmtAST>> ElseStmts;
@@ -217,6 +221,7 @@ std::unique_ptr<StmtAST> Parser::ParseIfStmt() {
         while (CurTok != tok_endif && CurTok != tok_eof) {
             auto Stmt = ParseStatement();
             if (Stmt) ElseStmts.push_back(std::move(Stmt));
+            else if (CurTok != tok_eof && CurTok != tok_endif) getNextToken();
         }
     }
 
@@ -244,6 +249,7 @@ std::unique_ptr<StmtAST> Parser::ParseWhileStmt() {
     while (CurTok != tok_endwhile && CurTok != tok_eof) {
         auto Stmt = ParseStatement();
         if (Stmt) Body.push_back(std::move(Stmt));
+        else if (CurTok != tok_eof && CurTok != tok_endwhile) getNextToken();
     }
 
     if (CurTok != tok_endwhile) {
@@ -262,6 +268,7 @@ std::unique_ptr<StmtAST> Parser::ParseRepeatStmt() {
     while (CurTok != tok_until && CurTok != tok_eof) {
         auto Stmt = ParseStatement();
         if (Stmt) Body.push_back(std::move(Stmt));
+        else if (CurTok != tok_eof && CurTok != tok_until) getNextToken();
     }
 
     if (CurTok != tok_until) {
@@ -307,12 +314,14 @@ std::unique_ptr<StmtAST> Parser::ParseForStmt() {
     if (CurTok == tok_step) {
         getNextToken();
         Step = ParseExpression();
+        if (!Step) return nullptr;
     }
 
     std::vector<std::unique_ptr<StmtAST>> Body;
     while (CurTok != tok_next && CurTok != tok_eof) {
         auto Stmt = ParseStatement();
         if (Stmt) Body.push_back(std::move(Stmt));
+        else if (CurTok != tok_eof && CurTok != tok_next) getNextToken();
     }
 
     if (CurTok != tok_next) {
@@ -342,6 +351,7 @@ std::unique_ptr<StmtAST> Parser::ParseStatement() {
     }
     else if (CurTok == tok_identifier) {
         std::string Name = Lex.IdentifierStr;
+        int Line = Lex.getLine();
         getNextToken();
         
         if (CurTok == '[') {
@@ -349,6 +359,7 @@ std::unique_ptr<StmtAST> Parser::ParseStatement() {
             std::vector<std::unique_ptr<ExprAST>> Indices;
             while (true) {
                 auto Exp = ParseExpression();
+                if (!Exp) return nullptr;
                 Indices.push_back(std::move(Exp));
                 if (CurTok == ']') break;
                 if (CurTok == ',') getNextToken();
@@ -361,12 +372,14 @@ std::unique_ptr<StmtAST> Parser::ParseStatement() {
             }
             getNextToken();
             auto Expr = ParseExpression();
-            return std::make_unique<ArrayAssignStmtAST>(Name, std::move(Indices), std::move(Expr));
+            if (!Expr) return nullptr;
+            return std::make_unique<ArrayAssignStmtAST>(Name, std::move(Indices), std::move(Expr), Line);
         }
         
         if (CurTok != tok_assign) return nullptr;
         getNextToken();
         auto Expr = ParseExpression();
+        if (!Expr) return nullptr;
         return std::make_unique<AssignStmtAST>(Name, std::move(Expr));
     }
     else if (CurTok == tok_input) {
@@ -379,6 +392,7 @@ std::unique_ptr<StmtAST> Parser::ParseStatement() {
     else if (CurTok == tok_output) {
         getNextToken();
         auto Expr = ParseExpression();
+        if (!Expr) return nullptr;
         return std::make_unique<OutputStmtAST>(std::move(Expr));
     }
     else if (CurTok == tok_if) {