From a3b4cd4fdd4340c952eaa00bca9bebf817b901ae Mon Sep 17 00:00:00 2001 From: Roland Reichwein Date: Sun, 15 Nov 2020 18:39:01 +0100 Subject: Fixed unit tests, prepared hierarchical evaluation via stack (WIP) --- Makefile | 7 +++-- asm/assembler.h | 18 ++++++++++++ asm/intel64/encode.cpp | 24 ++++++++------- asm/intel64/mov.cpp | 6 ++++ asm/intel64/xor.cpp | 15 ++++++++-- cpp.cpp | 79 ++++++++++++++++++++++++++++---------------------- flowgraph/graph.cpp | 60 ++++++++++++++++++++++++++++++++++++++ flowgraph/graph.h | 22 +++++++++++--- flowgraph/node.cpp | 8 +++++ flowgraph/node.h | 16 ++++++++-- flowgraph/scope.cpp | 28 ++++++++++++++++++ flowgraph/scope.h | 29 ++++++++++++++++++ flowgraph/storage.cpp | 9 ++++-- flowgraph/storage.h | 16 +++------- 14 files changed, 267 insertions(+), 70 deletions(-) create mode 100644 flowgraph/scope.cpp create mode 100644 flowgraph/scope.h diff --git a/Makefile b/Makefile index 7120470..f1ea2dc 100644 --- a/Makefile +++ b/Makefile @@ -75,6 +75,7 @@ PROGSRC=\ flowgraph/data.cpp \ flowgraph/graph.cpp \ flowgraph/node.cpp \ + flowgraph/scope.cpp \ flowgraph/storage.cpp \ file.cpp \ grammer.cpp \ @@ -101,10 +102,10 @@ all: mcc unittest systemtest # Tests on C++ level unittest: test-$(PROJECTNAME) - ./test-$(PROJECTNAME) --gtest_filter='CppTest.compile_2_times' + ./test-$(PROJECTNAME) # --gtest_filter='CppTest.compile_2_times' # Testing mcc executable and compiled elf programs -systemtest: +systemtest: mcc ./mcc systemtest/mcc-execute.tests/test-return-1.cpp ./mcc systemtest/mcc-execute.tests/test-addition.cpp runtest --srcdir systemtest --tool mcc # --all @@ -121,7 +122,7 @@ dep: $(MAKE) $(TESTSRC:.cpp=.d) mcc.d %.d: %.cpp - $(CXX) $(CXXFLAGS) $(CXXTESTFLAGS) -MM -MP -MF $@ -c $< + $(CXX) $(CXXFLAGS) $(CXXTESTFLAGS) -MM -MP -MF $@ -MT $(*D)/$(*F).o -c $< %.o: %.cpp %.d $(CXX) $(CXXFLAGS) $(CXXTESTFLAGS) -c $< -o $@ diff --git a/asm/assembler.h b/asm/assembler.h index aa886b5..bd291b8 100644 --- a/asm/assembler.h +++ b/asm/assembler.h @@ -4,6 +4,8 @@ #include "chunk.h" +#include "../minicc.h" + #include #include @@ -93,6 +95,22 @@ public: std::string m_name; }; + // 64 bit Ptr to 32 bit Memory + class Mem32Ptr64 + { + public: + Mem32Ptr64(const std::string& reg, int32_t offs = 0): m_reg(reg), m_offs(offs) {} + Mem32Ptr64(const std::string& reg, const std::string& reg2 = ""s, int32_t offs = 0): m_reg(reg), m_reg2(reg2), m_offs(offs) {} + std::string reg() { return m_reg; } + std::string reg2() { return m_reg2; } + int32_t offs() { return m_offs; } + + private: + std::string m_reg; + std::string m_reg2; + int32_t m_offs; + }; + class Label { public: diff --git a/asm/intel64/encode.cpp b/asm/intel64/encode.cpp index 123dff2..03a7897 100644 --- a/asm/intel64/encode.cpp +++ b/asm/intel64/encode.cpp @@ -37,7 +37,7 @@ void Asm::toMachineCode(const FlowGraph::Graph& graph, Segment& segment) std::runtime_error("Bad value for operand 1: Constant expected"); } - if (op.type() == FlowGraph::UnaryOperationType::Store) { + if (op.type() == FlowGraph::UnaryOperationType::Negate) { Asm::Args args1{{Asm::Args::Register32("edi"), Asm::Args::Immediate32(immediate1)}}; segment.push_back(makeOp("mov", args1)); } else @@ -84,16 +84,14 @@ void Asm::toMachineCode(const FlowGraph::Graph& graph, Segment& segment) std::runtime_error("Bad value for operand 2: Constant expected"); } - Asm::Args args1{{Asm::Args::Register32("edi"), Asm::Args::Immediate32(immediate1)}}; - segment.push_back(makeOp("mov", args1)); + segment.push_back(makeOp("mov", Asm::Args{{Asm::Args::Register32("edi"), Asm::Args::Immediate32(immediate1)}})); - Asm::Args args2{{Asm::Args::Register32("edi"), Asm::Args::Immediate32(immediate2)}}; - - if (op.type() == FlowGraph::BinaryOperationType::Add) - segment.push_back(makeOp("add", args2)); - else if (op.type() == FlowGraph::BinaryOperationType::Multiply) - segment.push_back(makeOp("mul", args2)); - else + if (op.type() == FlowGraph::BinaryOperationType::Add) { + segment.push_back(makeOp("add", Asm::Args{{Asm::Args::Register32("edi"), Asm::Args::Immediate32(immediate2)}})); + } else if (op.type() == FlowGraph::BinaryOperationType::Multiply) { + segment.push_back(makeOp("mov", Asm::Args{{Asm::Args::Register32("ebx"), Asm::Args::Immediate32(immediate2)}})); + segment.push_back(makeOp("mul", Asm::Args{{Asm::Args::Register32("ebx")}})); + } else throw std::runtime_error("ICE: Asm: Unsupported binary operation type: "s + std::to_string(static_cast(op.type()))); } else if (typeid(node_deref) == typeid(FlowGraph::CreateScopeOp)) { @@ -104,6 +102,12 @@ void Asm::toMachineCode(const FlowGraph::Graph& graph, Segment& segment) } else if (typeid(node_deref) == typeid(FlowGraph::DestroyScopeOp)) { //FlowGraph::DestroyScopeOp& op {dynamic_cast(*node)}; segment.push_back(makeOp("pop", Asm::Args{{Asm::Args::Register64("rbp")}})); + + // Move + segment.push_back(makeOp("xor", Asm::Args{{Asm::Args::Register64("rdi"), Asm::Args::Register64("rdi")}})); + segment.push_back(makeOp("mov", Asm::Args{{Asm::Args::Register32("edi"), Asm::Args::Register32("eax")}})); + } else if (typeid(node_deref) == typeid(FlowGraph::DataNode)) { + // ignore: Immediate data is used in subsequent nodes } else { throw std::runtime_error("ICE: Encoding: Unsupported node: "s + demangle(typeid(node_deref))); } diff --git a/asm/intel64/mov.cpp b/asm/intel64/mov.cpp index 5b224c1..6426238 100644 --- a/asm/intel64/mov.cpp +++ b/asm/intel64/mov.cpp @@ -43,6 +43,12 @@ bool registered { registerOp(mangleName("mov"), [](const Asm::Args& args) -> std::shared_ptr{ return std::make_shared(args); }) && + registerOp(mangleName("mov"), [](const Asm::Args& args) -> std::shared_ptr{ + return std::make_shared(args); + }) && + registerOp(mangleName("mov"), [](const Asm::Args& args) -> std::shared_ptr{ + return std::make_shared(args); + }) && registerOp(mangleName("mov"), [](const Asm::Args& args) -> std::shared_ptr{ return std::make_shared(args); }) && diff --git a/asm/intel64/xor.cpp b/asm/intel64/xor.cpp index aba6fb5..1628558 100644 --- a/asm/intel64/xor.cpp +++ b/asm/intel64/xor.cpp @@ -12,9 +12,14 @@ using namespace std::string_literals; Op_xor::Op_xor(const Asm::Args& args) { if (args[0].type() == typeid(Asm::Args::Register8) && args[1].type() == typeid(Asm::Args::Register8)) { // xor reg8, reg8 - // r8, r/m8: ModRM:reg (w), ModRM:r/m (r) - machine_code = std::vector{ 0x32 } + + machine_code = std::vector{ 0x30 } + ModRM(std::any_cast(args[0]).name(), std::any_cast(args[1]).name()); + } else if (args[0].type() == typeid(Asm::Args::Register32) && args[1].type() == typeid(Asm::Args::Register32)) { // xor reg32, reg32 + machine_code = std::vector{ 0x31 } + + ModRM(std::any_cast(args[0]).name(), std::any_cast(args[1]).name()); + } else if (args[0].type() == typeid(Asm::Args::Register64) && args[1].type() == typeid(Asm::Args::Register64)) { // xor reg64, reg64 + machine_code = REX("W") + std::vector{ 0x31 } + + ModRM(std::any_cast(args[0]).name(), std::any_cast(args[1]).name()); } else { throw std::runtime_error("Unimplemented: xor "s + args[0].type().name() + " "s + args[1].type().name()); } @@ -25,6 +30,12 @@ namespace { bool registered { registerOp(mangleName("xor"), [](const Asm::Args& args) -> std::shared_ptr{ return std::make_shared(args); + }) && + registerOp(mangleName("xor"), [](const Asm::Args& args) -> std::shared_ptr{ + return std::make_shared(args); + }) && + registerOp(mangleName("xor"), [](const Asm::Args& args) -> std::shared_ptr{ + return std::make_shared(args); }) }; diff --git a/cpp.cpp b/cpp.cpp index 4bb8a01..9690289 100644 --- a/cpp.cpp +++ b/cpp.cpp @@ -400,18 +400,29 @@ std::unordered_map> CPP::getNodeEv { "multiplicative-expression", [&](index_t index) -> std::any { if (childTypesOfNodeMatch(index, {"multiplicative-expression", "*", "pm-expression"})) { - if (getValue(index, 0).type() != typeid(FlowGraph::Data)) + if (getValue(index, 0).type() != typeid(FlowGraph::Graph)) throw std::runtime_error("ICE: multiplicative-expression: Bad data type for argument 1: "s + demangle(getValue(index, 0).type())); - if (getValue(index, 2).type() != typeid(FlowGraph::Data)) + if (getValue(index, 2).type() != typeid(FlowGraph::Graph)) throw std::runtime_error("ICE: multiplicative-expression: Bad data type for argument 3: "s + demangle(getValue(index, 2).type())); - FlowGraph::LocalScope scope; // TODO: move to context! - FlowGraph::Data destination{FlowGraph::MakeTemporaryInt(scope)}; - FlowGraph::Data value0 {std::any_cast(getValue(index, 0))}; - FlowGraph::Data value1 {std::any_cast(getValue(index, 2))}; + FlowGraph::Graph value0{std::any_cast(getValue(index, 0))}; + std::shared_ptr lastOp0{value0.lastOp()}; - std::shared_ptr node {std::make_shared(FlowGraph::BinaryOperationType::Multiply, destination, value0, value1)}; - return node; + FlowGraph::Graph value1{std::any_cast(getValue(index, 2))}; + std::shared_ptr lastOp1{value1.lastOp()}; + + FlowGraph::Graph result{value0}; + result.append(value1); + + FlowGraph::Data destination{FlowGraph::MakeTemporaryInt(result.scope())}; + + std::shared_ptr node {std::make_shared(FlowGraph::BinaryOperationType::Multiply, + destination, + lastOp0->destination(), lastOp1->destination())}; + + result.append(node); + + return result; } if (childTypesOfNodeMatch(index, {"pm-expression"})) return getValue(index, 0); @@ -421,18 +432,29 @@ std::unordered_map> CPP::getNodeEv { "additive-expression", [&](index_t index) -> std::any { if (childTypesOfNodeMatch(index, {"additive-expression", "+", "multiplicative-expression"})) { - if (getValue(index, 0).type() != typeid(FlowGraph::Data)) + if (getValue(index, 0).type() != typeid(FlowGraph::Graph)) throw std::runtime_error("ICE: additive-expression: Bad data type for argument 1: "s + demangle(getValue(index, 0).type())); - if (getValue(index, 2).type() != typeid(FlowGraph::Data)) + if (getValue(index, 2).type() != typeid(FlowGraph::Graph)) throw std::runtime_error("ICE: additive-expression: Bad data type for argument 3: "s + demangle(getValue(index, 2).type())); - FlowGraph::LocalScope scope; // TODO: move to context! - FlowGraph::Data destination{FlowGraph::MakeTemporaryInt(scope)}; - FlowGraph::Data value0 {std::any_cast(getValue(index, 0))}; - FlowGraph::Data value1 {std::any_cast(getValue(index, 2))}; + FlowGraph::Graph value0{std::any_cast(getValue(index, 0))}; + std::shared_ptr lastOp0{value0.lastOp()}; + + FlowGraph::Graph value1{std::any_cast(getValue(index, 2))}; + std::shared_ptr lastOp1{value1.lastOp()}; + + FlowGraph::Graph result{value0}; + result.append(value1); - std::shared_ptr node {std::make_shared(FlowGraph::BinaryOperationType::Add, destination, value0, value1)}; - return node; + FlowGraph::Data destination{FlowGraph::MakeTemporaryInt(result.scope())}; + + std::shared_ptr node {std::make_shared(FlowGraph::BinaryOperationType::Add, + destination, + lastOp0->destination(), lastOp1->destination())}; + + result.append(node); + + return result; } if (childTypesOfNodeMatch(index, {"multiplicative-expression"})) return getValue(index, 0); @@ -519,27 +541,13 @@ std::unordered_map> CPP::getNodeEv { "expression", [&](index_t index) -> std::any { if (childTypesOfNodeMatch(index, {"assignment-expression"})) { - std::shared_ptr scope_node {std::make_shared()}; - mCPPContext.graph.push_back(scope_node); - - FlowGraph::LocalScope& scope{scope_node->scope()}; - - if (getValue(index, 0).type() == typeid(FlowGraph::Data)) { // got Data -> make trivial Node out of it and return it - - FlowGraph::Data destination{FlowGraph::MakeTemporaryInt(scope)}; - FlowGraph::Data source {std::any_cast(getValue(index, 0))}; - - std::shared_ptr node {std::make_shared(FlowGraph::UnaryOperationType::Store, destination, source)}; - mCPPContext.graph.push_back(node); - return node; - } else if (getValue(index, 0).type() == typeid(std::shared_ptr)) { - std::shared_ptr node {std::any_cast>(getValue(index, 0))}; - mCPPContext.graph.push_back(node); - return getValue(index, 0); + if (getValue(index, 0).type() == typeid(FlowGraph::Graph)) { + FlowGraph::Graph graph {std::any_cast(getValue(index, 0))}; + mCPPContext.graph = graph; + return graph; } else { throw std::runtime_error("ICE: expression: Unsupported argument type: "s + demangle(getValue(index, 0).type())); } - mCPPContext.graph.push_back(std::make_shared(scope)); } throw std::runtime_error("ICE: Unsupported childs: "s + ruleString(index)); // TODO } @@ -576,7 +584,8 @@ void CPP::getValueOfToken(index_t index) if (m_tokens[index].type == "literal") { // TODO: also support other types, different from Int FlowGraph::Data data{FlowGraph::MakeConstantInt(stoi(m_tokens[index].value))}; - mValues.push_back(data); + FlowGraph::Graph graph{{std::make_shared(data)}}; + mValues.push_back(graph); } else { mValues.push_back(std::any{}); } diff --git a/flowgraph/graph.cpp b/flowgraph/graph.cpp index e8b6b5e..6398c68 100644 --- a/flowgraph/graph.cpp +++ b/flowgraph/graph.cpp @@ -1 +1,61 @@ #include "graph.h" + +#include "minicc.h" +#include "node.h" + +#include + +using namespace std::string_literals; + +FlowGraph::Graph::Graph() +{ +} + +FlowGraph::Graph::Graph(const std::deque>& nodes): std::deque>(nodes) +{ + auto createLocalScope {std::make_shared()}; + this->push_front(createLocalScope); + + auto destroyLocalScope {std::make_shared(createLocalScope->scope())}; + this->push_back(destroyLocalScope); +} + +FlowGraph::Graph::~Graph() +{ +} + +// Assume first node of graph to be CreateScopeOp +FlowGraph::LocalScope& FlowGraph::Graph::scope() const +{ + if (this->empty()) + throw std::runtime_error("ICE: FlowGraph expected to be non-empty!"); + + auto& front_deref {*front()}; + + if (typeid(front_deref) != typeid(FlowGraph::CreateScopeOp)) + throw std::runtime_error("ICE: Bad type of first graph element: "s + demangle(typeid(front_deref))); + + FlowGraph::CreateScopeOp& createScope {dynamic_cast(front_deref)}; + + return createScope.scope(); +} + +void FlowGraph::Graph::append(const FlowGraph::Graph& other) +{ + this->insert(this->end() - 1, other.begin() + 1, other.end() - 1); + + this->scope().append(other.scope()); +} + +void FlowGraph::Graph::append(std::shared_ptr node) +{ + this->insert(this->end() - 1, node); +} + +std::shared_ptr FlowGraph::Graph::lastOp() const +{ + if (size() >= 3) + return *(end() - 2); + + throw std::runtime_error("ICE: No last operation found in graph"); +} diff --git a/flowgraph/graph.h b/flowgraph/graph.h index 265a3bd..15c6aef 100644 --- a/flowgraph/graph.h +++ b/flowgraph/graph.h @@ -2,18 +2,32 @@ #include "node.h" +#include #include #include -#include #include -#include namespace FlowGraph { - class Graph: public std::vector> + class Graph: public std::deque> { public: - Graph() {} + Graph(); + Graph(const std::deque>& nodes); + Graph(const Graph& other) = default; + ~Graph(); + + Graph& operator= (const Graph&) = default; + + // returns the outermost scope inside this graph + LocalScope& scope() const; + + // append other graph by joining the respective outermost scopes + void append(const Graph& other); + + void append(std::shared_ptr node); + + std::shared_ptr lastOp() const; }; } diff --git a/flowgraph/node.cpp b/flowgraph/node.cpp index 9b68d74..e0912dc 100644 --- a/flowgraph/node.cpp +++ b/flowgraph/node.cpp @@ -6,6 +6,14 @@ using namespace FlowGraph; +FlowGraph::Data& Node::destination() +{ + if (mOperands.size() < 1) + throw std::runtime_error("ICE: No destination operand available"); + + return mOperands[0]; +} + // 4 byte for now Data FlowGraph::MakeConstantInt(int i) { diff --git a/flowgraph/node.h b/flowgraph/node.h index 77395f0..5ea194d 100644 --- a/flowgraph/node.h +++ b/flowgraph/node.h @@ -19,8 +19,11 @@ namespace FlowGraph { public: Node(){} Node(std::vector operands): mOperands(operands) {} - std::vector& operands() { return mOperands; } virtual ~Node() {}; // force class to be polymorphic (e.g. in a container) + + std::vector& operands() { return mOperands; } + Data& destination(); // best-effort return of result/destination; else throw + private: std::vector mOperands; }; @@ -115,7 +118,6 @@ namespace FlowGraph { Increment, Decrement, Negate, - Store // just take Data as-is to store it at destination }; class UnaryOperation: public Node @@ -130,6 +132,16 @@ namespace FlowGraph { UnaryOperationType m_type; }; + // Just take a value e.g. Immediate and store it for later use. + // Should be optimized out later. + class DataNode: public Node + { + public: + DataNode(Data& value): + Node(std::vector({value})) + {} + }; + enum class BinaryOperationType: int { Add, diff --git a/flowgraph/scope.cpp b/flowgraph/scope.cpp new file mode 100644 index 0000000..6c2e30c --- /dev/null +++ b/flowgraph/scope.cpp @@ -0,0 +1,28 @@ +#include "scope.h" + +#include "storage.h" + +void FlowGraph::LocalScope::push_back(std::shared_ptr data) +{ + m_variables.push_back(data); +} + +void FlowGraph::LocalScope::append(const FlowGraph::LocalScope& other) +{ + m_variables.insert(m_variables.end(), other.m_variables.begin(), other.m_variables.end()); +} + +index_t FlowGraph::LocalScope::indexOfStorage(const TemporaryStorage& storage) const +{ + for (index_t i = 0; i < m_variables.size(); i++) { + FlowGraph::Storage& i_storage {*(m_variables[i]->storage())}; + + if (typeid(i_storage) == typeid(FlowGraph::TemporaryStorage)) { + FlowGraph::TemporaryStorage& temporaryStorage{dynamic_cast(i_storage)}; + if (&temporaryStorage == &storage) // compare addresses + return i; + } + } + + throw std::runtime_error("ICE: Storage not found"); +} diff --git a/flowgraph/scope.h b/flowgraph/scope.h new file mode 100644 index 0000000..50003f4 --- /dev/null +++ b/flowgraph/scope.h @@ -0,0 +1,29 @@ +#pragma once + +#include "data.h" + +#include "minicc.h" + +#include +#include +#include + +namespace FlowGraph { + + class TemporaryStorage; ///< Forward declaration + + // Provide a context for local temporaries name generation + class LocalScope + { + public: + LocalScope() = default; + + void push_back(std::shared_ptr data); + void append(const LocalScope& other); + index_t indexOfStorage(const TemporaryStorage& storage) const; + + private: + std::vector> m_variables; + }; + +} diff --git a/flowgraph/storage.cpp b/flowgraph/storage.cpp index f78a65d..7e502de 100644 --- a/flowgraph/storage.cpp +++ b/flowgraph/storage.cpp @@ -3,6 +3,11 @@ using namespace std::string_literals; FlowGraph::TemporaryStorage::TemporaryStorage(LocalScope& scope): - m_name("__local_"s + std::to_string(scope.getNewIndex())) -{} + m_scope(scope) +{ +} +std::string FlowGraph::TemporaryStorage::name() const +{ + return "__local_"s + std::to_string(m_scope.indexOfStorage(*this)); +} diff --git a/flowgraph/storage.h b/flowgraph/storage.h index fd3c085..7f648b0 100644 --- a/flowgraph/storage.h +++ b/flowgraph/storage.h @@ -2,6 +2,7 @@ #pragma once #include "data.h" +#include "scope.h" #include #include @@ -37,16 +38,7 @@ namespace FlowGraph { std::string m_name; }; - // Provide a context for local temporaries name generation - class LocalScope - { - public: - LocalScope() = default; - size_t getNewIndex() { return m_index++; } - private: - size_t m_index{ 0 }; - }; - + // named values class LocalStorage : public Storage { public: @@ -62,9 +54,9 @@ namespace FlowGraph { { public: TemporaryStorage(LocalScope& scope); - const std::string& name() const { return m_name; } + std::string name() const; private: - std::string m_name; + LocalScope& m_scope; }; // dereferenced pointer -- cgit v1.2.3