From 12232668d931b0f3593807d2096a2c2f26844b0b Mon Sep 17 00:00:00 2001 From: Martin Dobrev Date: Sun, 18 Nov 2018 20:32:58 +0200 Subject: Code generation improvements (#56) * Implement code generation for some unary expressions Implement debug code augmentation. Now part of expresions have source location. Extend Tokens with Column information. Refactor byte code generation. Add options for byte code generator. * Fix linux build * Little refactoring in byte code generation * Fix couple bugs in byte code generation and add some tests. * Fix some linux warnings. --- JSImpl/src/ByteCodeGenerator.cpp | 327 ++++++++++++++++++++++++++++----------- 1 file changed, 237 insertions(+), 90 deletions(-) (limited to 'JSImpl/src/ByteCodeGenerator.cpp') diff --git a/JSImpl/src/ByteCodeGenerator.cpp b/JSImpl/src/ByteCodeGenerator.cpp index 09901e1..dc846f2 100644 --- a/JSImpl/src/ByteCodeGenerator.cpp +++ b/JSImpl/src/ByteCodeGenerator.cpp @@ -1,13 +1,15 @@ #include "ByteCodeGenerator.h" #include "ExpressionVisitor.h" #include +#include +#include class ByteCodeGenerator : public ExpressionVisitor { public: - ByteCodeGenerator() {}; - ~ByteCodeGenerator() {}; + ByteCodeGenerator(const ByteCodeGeneratorOptions& o, const IPLVector& source) : m_Source(source), m_Options(o) {}; + ~ByteCodeGenerator() {}; virtual void Visit(FunctionDeclaration* e) override; virtual void Visit(BlockStatement* e) override; @@ -20,16 +22,19 @@ public: virtual void Visit(EmptyExpression* e) override { (void)e; } virtual void Visit(IfStatement* e) override; virtual void Visit(ForStatement* e) override; + virtual void Visit(UnaryExpression* e) override; IPLString GetCode(); unsigned ResolveRegisterName(IPLString& name); private: + void AddDebugInformation(Expression* e); struct Instruction { enum Type : char { - ADD, + FIRST = 0, + ADD = FIRST, SUB, MUL, DIV, @@ -67,56 +72,119 @@ private: CONST, STRING, HALT, + DEBUG, + LAST = DEBUG }; Type Descriptor; IPLString Args[3]; - double Number; + union + { + double Double[3]; + long long Int[3]; + unsigned long long Address[3]; + } Values; }; - size_t PushInstruction(Instruction::Type opcode, IPLString& arg1, IPLString& arg2, IPLString& arg3); + size_t PushInstruction(Instruction::Type opcode, const IPLString& arg1 = "", const IPLString& arg2 = "", const IPLString& arg3 = ""); size_t PushInstruction(Instruction::Type opcode, size_t Address); - size_t PushInstruction(Instruction::Type opcode, IPLString& arg1, size_t Address); + size_t PushInstruction(Instruction::Type opcode, const IPLString& arg1, size_t Address); + size_t PushInstruction(Instruction::Type opcode, int Int); + size_t PushInstruction(Instruction::Type opcode, const IPLString& arg0, double value); + void PushConst(double c); + IPLString CreateRegister(); + bool CheckOpCode(Instruction::Type opcode) { return opcode >= Instruction::Type::FIRST && opcode <= Instruction::Type::LAST; } private: IPLVector m_RegisterTable; IPLVector m_Code; + IPLVector m_Source; IPLStack m_RegisterStack; - unsigned m_CurrentStackPointer; IPLString m_OutputCode; + ByteCodeGeneratorOptions m_Options; }; -size_t ByteCodeGenerator::PushInstruction(Instruction::Type opcode, IPLString& arg0, IPLString& arg1, IPLString& arg2) +size_t ByteCodeGenerator::PushInstruction(Instruction::Type opcode, const IPLString& arg0, const IPLString& arg1, const IPLString& arg2) { + assert(CheckOpCode(opcode)); Instruction ins; ins.Descriptor = opcode; ins.Args[0] = arg0; ins.Args[1] = arg1; ins.Args[2] = arg2; - auto address = m_Code.size(); m_Code.push_back(ins); - return address; + return m_Code.size() - 1;; } size_t ByteCodeGenerator::PushInstruction(Instruction::Type opcode, size_t Address) { + assert(CheckOpCode(opcode)); Instruction ins; ins.Descriptor = opcode; - ins.Number = (double)Address; - auto address = m_Code.size(); + ins.Values.Address[0] = Address; m_Code.push_back(ins); - return address; + return m_Code.size() - 1;; } -size_t ByteCodeGenerator::PushInstruction(Instruction::Type opcode, IPLString& arg0, size_t Address) +size_t ByteCodeGenerator::PushInstruction(Instruction::Type opcode, int Int) { + assert(CheckOpCode(opcode)); + Instruction ins; + ins.Descriptor = opcode; + ins.Values.Int[0] = Int; + m_Code.push_back(ins); + return m_Code.size() - 1;; +} + +size_t ByteCodeGenerator::PushInstruction(Instruction::Type opcode, const IPLString& arg0, size_t Address) +{ + assert(CheckOpCode(opcode)); Instruction ins; ins.Descriptor = opcode; ins.Args[0] = arg0; - ins.Number = (double)Address; - auto address = m_Code.size(); + ins.Values.Address[0] = Address; + m_Code.push_back(ins); + return m_Code.size() - 1;; +} + +size_t ByteCodeGenerator::PushInstruction(Instruction::Type opcode, const IPLString& arg0, double value) +{ + assert(CheckOpCode(opcode)); + Instruction ins; + ins.Descriptor = opcode; + ins.Args[0] = arg0; + ins.Values.Double[0] = value; + m_Code.push_back(ins); + return m_Code.size() - 1;; +} + +void ByteCodeGenerator::PushConst(double c) +{ + IPLString regName = CreateRegister(); + m_RegisterStack.push(regName); + + PushInstruction(Instruction::Type::CONST, regName, c); +} + +IPLString ByteCodeGenerator::CreateRegister() +{ + IPLString regName = IPLString("tmp"); + regName += std::to_string(m_RegisterTable.size()); + m_RegisterTable.push_back(regName); + return regName; +} + +void ByteCodeGenerator::AddDebugInformation(Expression* e) +{ + if (!m_Options.AddDebugInformation || e->GetLine() == (unsigned)-1 || e->GetColumn() == (unsigned)-1) + { + return; + } + Instruction ins; + ins.Descriptor = Instruction::Type::DEBUG; + ins.Values.Int[0] = e->GetLine(); + ins.Values.Int[1] = e->GetColumn(); m_Code.push_back(ins); - return address; } void ByteCodeGenerator::Visit(FunctionDeclaration* e) @@ -146,19 +214,14 @@ void ByteCodeGenerator::Visit(TopStatements* e) { auto& statements = e->GetValues(); - Instruction current; - current.Descriptor = Instruction::Type::PUSH; - auto index = m_Code.size(); - m_Code.push_back(current); + auto startAddress = PushInstruction(Instruction::Type::PUSH, (int)0); for (auto& s : statements) { s->Accept(*this); } - m_Code[index].Number = (unsigned)m_RegisterTable.size(); + m_Code[startAddress].Values.Int[0] = (int)m_RegisterTable.size(); - current.Descriptor = Instruction::Type::POP; - current.Number = (unsigned)m_RegisterTable.size(); - m_Code.push_back(current); + PushInstruction(Instruction::Type::POP, (int)m_RegisterTable.size()); } void ByteCodeGenerator::Visit(VariableDefinitionExpression* e) @@ -166,6 +229,8 @@ void ByteCodeGenerator::Visit(VariableDefinitionExpression* e) auto it = std::find_if(m_RegisterTable.begin(), m_RegisterTable.end(), [&](IPLString& current) { return e->GetName() == current; }); + + if (it != m_RegisterTable.end()) { // TODO: error double definitions @@ -176,64 +241,50 @@ void ByteCodeGenerator::Visit(VariableDefinitionExpression* e) { e->GetValue()->Accept(*this); } + AddDebugInformation(e); if (!m_RegisterStack.empty()) { - Instruction current; - current.Descriptor = Instruction::Type::MOV; - current.Args[0] = e->GetName(); - current.Args[1] = m_RegisterStack.top(); + PushInstruction(Instruction::Type::MOV, e->GetName(), m_RegisterStack.top(), ""); m_RegisterStack.pop(); - m_Code.push_back(current); } } void ByteCodeGenerator::Visit(BinaryExpression* e) { - Instruction current; - - e->GetLeft()->Accept(*this); - current.Args[1] = m_RegisterStack.top(); - m_RegisterStack.pop(); - e->GetRight()->Accept(*this); - current.Args[2] = m_RegisterStack.top(); - m_RegisterStack.pop(); + auto r = m_RegisterStack.top(); + e->GetLeft()->Accept(*this); + auto l = m_RegisterStack.top(); + AddDebugInformation(e); if (e->GetOperator() == TokenType::Equal) { - current.Descriptor = Instruction::Type::MOV; - current.Args[0] = current.Args[1]; - current.Args[1] = current.Args[2]; - m_Code.push_back(current); + PushInstruction(Instruction::Type::MOV, l, r); return; } - - IPLString regName = IPLString ("tmp"); - regName += std::to_string(m_RegisterTable.size()); - m_RegisterTable.push_back(regName); - m_RegisterStack.push(regName); - current.Args[0] = regName; + IPLString o = CreateRegister(); + m_RegisterStack.push(o); switch (e->GetOperator()) { case TokenType::Plus: - current.Descriptor = Instruction::Type::ADD; - break; + PushInstruction(Instruction::Type::ADD, o, l, r); + return; case TokenType::Minus: - current.Descriptor = Instruction::Type::SUB; - break; + PushInstruction(Instruction::Type::SUB, o, l, r); + return; case TokenType::Star: - current.Descriptor = Instruction::Type::MUL; - break; + PushInstruction(Instruction::Type::MUL, o, l, r); + return; case TokenType::Division: - current.Descriptor = Instruction::Type::DIV; - break; + PushInstruction(Instruction::Type::DIV, o, l, r); + return; case TokenType::Less: - current.Descriptor = Instruction::Type::LESS; - break; + PushInstruction(Instruction::Type::LESS, o, l, r); + return; case TokenType::EqualEqual: - current.Descriptor = Instruction::Type::EQ; - break; + PushInstruction(Instruction::Type::EQ, o, l, r); + return; case TokenType::BangEqual: NOT_IMPLEMENTED; break; @@ -243,37 +294,28 @@ void ByteCodeGenerator::Visit(BinaryExpression* e) default: NOT_IMPLEMENTED; } - m_Code.push_back(current); } void ByteCodeGenerator::Visit(IfStatement* e) { - Instruction current; e->GetCondition()->Accept(*this); - current.Descriptor = Instruction::Type::JMPF; - current.Args[0] = m_RegisterStack.top(); - current.Number = 0.0; - m_RegisterStack.pop(); - auto ifIndex = m_Code.size(); - m_Code.push_back(current); + auto ifAddress = PushInstruction(Instruction::Type::JMPF, m_RegisterStack.top(), size_t(0)); e->GetIfStatement()->Accept(*this); if (e->GetElseStatement()) { - current.Descriptor = Instruction::Type::JMP; - m_Code.push_back(current); - auto afterTrueBlock = m_Code.size(); + auto blockEndAddress = PushInstruction(Instruction::Type::JMP); e->GetElseStatement()->Accept(*this); // Patching - m_Code[ifIndex].Number = (double)afterTrueBlock; - m_Code[afterTrueBlock - 1].Number = (double)m_Code.size(); + m_Code[ifAddress].Values.Address[0] = blockEndAddress + 1; + m_Code[blockEndAddress].Values.Address[0] = m_Code.size(); } else { - m_Code[ifIndex].Number = (double)m_Code.size(); + m_Code[ifAddress].Values.Address[0] = m_Code.size(); } } @@ -282,12 +324,12 @@ void ByteCodeGenerator::Visit(ForStatement* e) e->GetInitialization()->Accept(*this); auto compareAddress = m_Code.size(); e->GetCondition()->Accept(*this); - auto endAddress = PushInstruction(Instruction::Type::JMPF, m_RegisterStack.top(), 0); + auto endAddress = PushInstruction(Instruction::Type::JMPF, m_RegisterStack.top(), (size_t)0); m_RegisterStack.pop(); e->GetBody()->Accept(*this); e->GetIteration()->Accept(*this); PushInstruction(Instruction::Type::JMP, compareAddress); - m_Code[endAddress].Number = (double)m_Code.size(); + m_Code[endAddress].Values.Address[0] = m_Code.size(); } void ByteCodeGenerator::Visit(IdentifierExpression* e) @@ -297,12 +339,99 @@ void ByteCodeGenerator::Visit(IdentifierExpression* e) void ByteCodeGenerator::Visit(LiteralNumber* e) { - IPLString regName = IPLString("const"); - regName += std::to_string(m_RegisterTable.size()); - m_RegisterTable.push_back(regName); + AddDebugInformation(e); + IPLString regName = CreateRegister(); m_RegisterStack.push(regName); - PushInstruction(Instruction::Type::CONST, regName, (size_t)e->GetValue()); + PushInstruction(Instruction::Type::CONST, regName, e->GetValue()); +} + +void ByteCodeGenerator::Visit(UnaryExpression* e) +{ + AddDebugInformation(e); + e->GetExpr()->Accept(*this); + auto reg = m_RegisterStack.top(); + m_RegisterStack.pop(); + if (e->GetSuffix()) + { + switch (e->GetOperator()) + { + case TokenType::PlusPlus: + PushConst(1); + { + auto one = m_RegisterStack.top(); + m_RegisterStack.pop(); + auto o = CreateRegister(); + PushInstruction(Instruction::Type::MOV, o, reg); + m_RegisterStack.push(o); + PushInstruction(Instruction::Type::ADD, reg, reg, one); + } + return; + case TokenType::MinusMinus: + PushConst(1); + { + auto one = m_RegisterStack.top(); + m_RegisterStack.pop(); + auto o = CreateRegister(); + PushInstruction(Instruction::Type::MOV, o, reg); + m_RegisterStack.push(o); + PushInstruction(Instruction::Type::SUB, reg, reg, one); + } + return; + default: + NOT_IMPLEMENTED; + break; + } + } + else + { + // prefix + switch (e->GetOperator()) + { + case TokenType::Delete: + NOT_IMPLEMENTED; + return; + case TokenType::PlusPlus: + PushConst(1); + { + auto one = m_RegisterStack.top(); + m_RegisterStack.pop(); + m_RegisterStack.push(reg); + PushInstruction(Instruction::Type::ADD, reg, reg, one); + } + return; + case TokenType::MinusMinus: + PushConst(1); + { + auto one = m_RegisterStack.top(); + m_RegisterStack.pop(); + m_RegisterStack.push(reg); + PushInstruction(Instruction::Type::SUB, reg, reg, one); + } + return; + case TokenType::Void: + NOT_IMPLEMENTED; + return; + case TokenType::Typeof: + NOT_IMPLEMENTED; + return; + case TokenType::Plus: + NOT_IMPLEMENTED; + return; + case TokenType::Minus: + NOT_IMPLEMENTED; + return; + case TokenType::BitwiseNot: + NOT_IMPLEMENTED; + return; + case TokenType::Bang: + NOT_IMPLEMENTED; + return; + default: + NOT_IMPLEMENTED; + break; + } + } } unsigned ByteCodeGenerator::ResolveRegisterName(IPLString& name) @@ -319,14 +448,16 @@ IPLString ByteCodeGenerator::GetCode() auto programCounter = 0; for (auto& i : m_Code) { - result += std::to_string(programCounter) + ": "; + if (i.Descriptor != ByteCodeGenerator::Instruction::DEBUG) + { + result += std::to_string(programCounter) + ": "; + } switch (i.Descriptor) { case ByteCodeGenerator::Instruction::ADD: result += "add r" + std::to_string(ResolveRegisterName(i.Args[0])) + " r" + std::to_string(ResolveRegisterName(i.Args[1])) + " r" + std::to_string(ResolveRegisterName(i.Args[2])) + '\n'; - break; case ByteCodeGenerator::Instruction::SUB: result += "sub r" + std::to_string(ResolveRegisterName(i.Args[0])) @@ -368,25 +499,25 @@ IPLString ByteCodeGenerator::GetCode() NOT_IMPLEMENTED; break; case ByteCodeGenerator::Instruction::JMP: - result += "jmp " + std::to_string((size_t)i.Number) + '\n'; + result += "jmp " + std::to_string(i.Values.Address[0]) + '\n'; break; case ByteCodeGenerator::Instruction::JMPT: result += "jmpt r" + std::to_string(ResolveRegisterName(i.Args[0])) - + " " + std::to_string((size_t)i.Number) + '\n'; + + " " + std::to_string(i.Values.Address[0]) + '\n'; break; case ByteCodeGenerator::Instruction::JMPF: result += "jmpf r" + std::to_string(ResolveRegisterName(i.Args[0])) - + " " + std::to_string((size_t)i.Number) + '\n'; + + " " + std::to_string(i.Values.Address[0]) + '\n'; break; case ByteCodeGenerator::Instruction::DUP: result += "dup"; NOT_IMPLEMENTED; break; case ByteCodeGenerator::Instruction::PUSH: - result += "push " + std::to_string((size_t)i.Number) + '\n'; + result += "push " + std::to_string(i.Values.Int[0]) + '\n'; break; case ByteCodeGenerator::Instruction::POP: - result += "pop " + std::to_string((size_t)i.Number) + '\n'; + result += "pop " + std::to_string(i.Values.Int[0]) + '\n'; break; case ByteCodeGenerator::Instruction::SAVE: result += "save"; @@ -471,7 +602,7 @@ IPLString ByteCodeGenerator::GetCode() NOT_IMPLEMENTED; break; case ByteCodeGenerator::Instruction::CONST: - result += "const r" + std::to_string(ResolveRegisterName(i.Args[0])) + " " + std::to_string(i.Number) + '\n'; + result += "const r" + std::to_string(ResolveRegisterName(i.Args[0])) + " " + std::to_string(i.Values.Double[0]) + '\n'; break; case ByteCodeGenerator::Instruction::STRING: result += "string"; @@ -480,6 +611,13 @@ IPLString ByteCodeGenerator::GetCode() case ByteCodeGenerator::Instruction::HALT: result += "halt\n"; break; + case ByteCodeGenerator::Instruction::DEBUG: + { + auto line = i.Values.Int[0]; + auto column = i.Values.Int[1]; + result += "D: " + m_Source[line].substr(0, column) + "@@=>" + m_Source[line].substr(column, m_Source[line].size()) + '\n'; + } + break; default: NOT_IMPLEMENTED; break; @@ -492,9 +630,18 @@ IPLString ByteCodeGenerator::GetCode() return result; } -IPLString GenerateByteCode(ExpressionPtr program) +IPLString GenerateByteCode(ExpressionPtr program, const IPLString& source, const ByteCodeGeneratorOptions& options) { - ByteCodeGenerator generator; + std::istringstream sourceStream(source); + + IPLVector sourceByLines; + while (sourceStream.good()) + { + IPLString currentLine; + std::getline(sourceStream, currentLine); + sourceByLines.push_back(currentLine); + } + ByteCodeGenerator generator(options, sourceByLines); program->Accept(generator); return generator.GetCode(); -- cgit v1.3.1-23-gd82d