Add FlowGraph

17 files changed, 387 insertions, 7 deletions

diff --git a/Makefile b/Makefile
index 38e5759..316e21b 100644
--- a/Makefile
+++ b/Makefile
@@ -63,19 +63,24 @@ PROGSRC=\
     coff.cpp \
     debug.cpp \
     elf.cpp \
+    flowgraph/data.cpp \
+    flowgraph/graph.cpp \
+    flowgraph/node.cpp \
+    flowgraph/storage.cpp \
     file.cpp \
     grammer.cpp \
     lexer.cpp \
     minicc.cpp \
 
 TESTSRC=\
-    test-cpp.cpp \
-    test-cppbnf.cpp \
-    test-elf.cpp \
-    test-grammer.cpp \
-    test-lexer.cpp \
-    test-minicc.cpp \
-    test-asm.cpp \
+    tests/test-cpp.cpp \
+    tests/test-cppbnf.cpp \
+    tests/test-elf.cpp \
+    tests/test-flowgraph.cpp \
+    tests/test-grammer.cpp \
+    tests/test-lexer.cpp \
+    tests/test-minicc.cpp \
+    tests/test-asm.cpp \
     googlemock/src/gmock-all.cpp \
     googletest/src/gtest-all.cpp \
     $(PROGSRC)
diff --git a/flowgraph/data.cpp b/flowgraph/data.cpp
new file mode 100644
index 0000000..9dd6ef8
--- /dev/null
+++ b/flowgraph/data.cpp
@@ -0,0 +1 @@
+#include "data.h"
diff --git a/flowgraph/data.h b/flowgraph/data.h
new file mode 100644
index 0000000..353567c
--- /dev/null
+++ b/flowgraph/data.h
@@ -0,0 +1,51 @@
+#pragma once
+
+#include <cstdint>
+#include <vector>
+
+namespace FlowGraph {
+
+ // Explicitely not including size
+ enum class DataType
+ {
+  Size,
+  Int,
+  UInt,
+  Pointer,
+  Bool,
+  Char,
+  UChar,
+ };
+
+ class Storage; ///< forward declaration
+
+ // Argument for Operations
+ // -> includes identity of data point, e.g. a local int variable
+ // Built up as a list of Data instances for global and local data points in parallel to FlowGraph
+ class Data
+ {
+ public:
+  Data(DataType type, std::shared_ptr<Storage> storage):m_type(type) {}
+  DataType type() const { return m_type; }
+ private:
+  const DataType m_type;
+  std::shared_ptr<Storage> m_storage;
+ };
+
+}
+
+namespace GlobalData {
+
+ // variable of simple or struct type
+ class Element
+ {
+ private:
+  size_t size;
+  std::vector<uint8_t> data; // may be empty if uninitialized
+ };
+
+ class Segment: public std::vector<Element>
+ {
+ };
+
+}
diff --git a/flowgraph/graph.cpp b/flowgraph/graph.cpp
new file mode 100644
index 0000000..e8b6b5e
--- /dev/null
+++ b/flowgraph/graph.cpp
@@ -0,0 +1 @@
+#include "graph.h"
diff --git a/flowgraph/graph.h b/flowgraph/graph.h
new file mode 100644
index 0000000..265a3bd
--- /dev/null
+++ b/flowgraph/graph.h
@@ -0,0 +1,20 @@
+#pragma once
+
+#include "node.h"
+
+#include <exception>
+#include <memory>
+#include <string>
+#include <stdexcept>
+#include <vector>
+
+namespace FlowGraph {
+
+ class Graph: public std::vector<std::shared_ptr<Node>>
+ {
+ public:
+  Graph() {}
+ };
+
+}
+
diff --git a/flowgraph/node.cpp b/flowgraph/node.cpp
new file mode 100644
index 0000000..fc55ef6
--- /dev/null
+++ b/flowgraph/node.cpp
@@ -0,0 +1,9 @@
+#include "node.h"
+
+#include "data.h"
+
+using namespace FlowGraph;
+
+Data FlowGraph::MakeLocalPointer(const std::string& name) { return Data(DataType::Pointer, std::make_shared<LocalStorage>(name)); }
+Data FlowGraph::MakeLocalSize(const std::string& name) { return Data(DataType::Size, std::make_shared<LocalStorage>(name)); }
+
diff --git a/flowgraph/node.h b/flowgraph/node.h
new file mode 100644
index 0000000..37af95a
--- /dev/null
+++ b/flowgraph/node.h
@@ -0,0 +1,150 @@
+#pragma once
+
+#include "data.h"
+#include "storage.h"
+
+namespace FlowGraph {
+
+ // Node in Graph: Building block of the graph
+ // Abstracts actions of program flow, yet machine independent,
+ // to be converted later into machine code
+ // Basic elements:
+ // - Subroutine calls
+ // - Arithmetic/logical operations
+ // Arguments (Data instances) will be provided explicitly from outside
+ class Node
+ {
+ public:
+  virtual ~Node() {}; // force class to be polymorphic
+ };
+ 
+ // Memory on Heap: new and delete
+ class AllocateDynamic: public Node
+ {
+ public:
+  AllocateDynamic(Data& location, Data& size): m_location(location), m_size(size) {}
+ private:
+  Data m_location; // in/out: Pointer
+  Data m_size; // in: Size
+ };
+
+ class DeallocateDynamic: public Node
+ {
+ public:
+  DeallocateDynamic(Data& location) : m_location(location) {} // in
+ private:
+  Data m_location; // in: Pointer
+ };
+
+ Data MakeLocalPointer(const std::string& name);
+ Data MakeLocalSize(const std::string& name);
+
+ class MemCopy: public Node
+ {
+ public:
+  MemCopy(Data& destination, Data& source, Data& size): m_destination(destination), m_source(source), m_size(size) {}
+ private:
+  Data m_destination; // Pointer
+  Data m_source;      // Pointer
+  Data m_size;        // in bytes
+ };
+
+ class Move: public Node
+ {
+ public:
+  Move(Data& destination, Data& source): m_destination(destination), m_source(source) {}
+ private:
+  Data m_destination;
+  Data m_source;
+ };
+
+ enum class JumpVariant
+ {
+  Unconditional,
+  GT,
+  LT,
+  GE,
+  LE,
+  EQ,
+  NE
+ };
+
+ // Unconditional Jump, conditional Jump
+ class Jump: public Node
+ {
+ public:
+  Jump(JumpVariant variant, Data& source0, Data& source1, std::shared_ptr<Node> destination):
+   m_variant(variant),
+   m_source0(source0),
+   m_source1(source1),
+   m_destination(destination)
+  {}
+ private:
+  JumpVariant m_variant;
+  Data m_source0;
+  Data m_source1;
+  std::shared_ptr<Node> m_destination; // successor on branch
+ };
+ 
+ // Call Subroutine
+ class Call: public Node
+ {
+ public:
+  Call(std::shared_ptr<Node> destination, std::vector<Data> arguments): m_destination(destination), m_arguments(arguments) {}
+ private:
+  std::shared_ptr<Node> m_destination;
+  std::vector<Data> m_arguments;
+ };
+ 
+ // Return from Subroutine
+ class Return: public Node
+ {
+ public:
+  Return(std::vector<Data> returnValues): m_returnValues(returnValues) {}
+ private:
+  std::vector<Data> m_returnValues;
+ };
+ 
+ enum class UnaryOperationType {
+  Increment,
+  Decrement,
+  Negate
+ };
+
+ class UnaryOperation: public Node
+ {
+ public:
+  UnaryOperation(Data& destination, Data& source): m_destination(destination), m_source(source) {}
+ private:
+  Data m_destination;
+  Data m_source;
+ };
+
+ enum class BinaryOperationType {
+  Add,
+  Subtract,
+  Multiply,
+  Divide,
+  Modulo,
+  ShiftRight,
+  ShiftLeft,
+  BitwiseAnd,
+  BitwiseOr,
+  BitwiseXor,
+  BitwiseNot,
+  LogicalAnd,
+  LogicalOr,
+  LogicalNot
+ };
+
+ class BinaryOperation: public Node
+ {
+ public:
+  BinaryOperation(Data& destination, Data& source0, Data& source1): m_destination(destination), m_source0(source0), m_source1(source1) {}
+ private:
+  Data m_destination;
+  Data m_source0;
+  Data m_source1;
+ };
+
+}
diff --git a/flowgraph/storage.cpp b/flowgraph/storage.cpp
new file mode 100644
index 0000000..f78a65d
--- /dev/null
+++ b/flowgraph/storage.cpp
@@ -0,0 +1,8 @@
+#include "storage.h"
+
+using namespace std::string_literals;
+
+FlowGraph::TemporaryStorage::TemporaryStorage(LocalScope& scope):
+ m_name("__local_"s + std::to_string(scope.getNewIndex()))
+{}
+
diff --git a/flowgraph/storage.h b/flowgraph/storage.h
new file mode 100644
index 0000000..c2fa7c5
--- /dev/null
+++ b/flowgraph/storage.h
@@ -0,0 +1,85 @@
+#pragma once
+
+#include "data.h"
+
+#include <cstdint>
+#include <string>
+#include <vector>
+
+namespace FlowGraph {
+
+ // Parameter to Data class, defining where the data is stored
+ // Explicitely not including size
+ // But including label/data/pointer
+ // -> includes identity of certain data point
+ class Storage
+ {
+ public:
+  virtual ~Storage() {} // force class to be polymorphic
+ };
+
+ class Constant: public Storage
+ {
+ public:
+  Constant(std::vector<uint8_t> value) {} // little endian data
+  const std::vector<uint8_t>& value() const { return m_value; }
+ private:
+  std::vector<uint8_t> m_value;
+ };
+
+ class GlobalStorage : public Storage
+ {
+ public:
+  GlobalStorage(const std::string& name): m_name(name) {}
+  const std::string& name() const { return m_name; }
+ private:
+  std::string m_name;
+ };
+
+ class LocalStorage : public Storage
+ {
+ public:
+  LocalStorage(const std::string& name): m_name(name) {}
+  const std::string& name() const { return m_name; }
+ private:
+  std::string m_name;
+ };
+
+ // Provide a context for local temporaries name generation
+ class LocalScope
+ {
+ public:
+  size_t getNewIndex() { return m_index++; }
+ private:
+  size_t m_index{ 0 };
+ };
+
+ // intermediate results, anonymous values
+ // use generated name
+ class TemporaryStorage : public Storage
+ {
+ public:
+  TemporaryStorage(LocalScope& scope);
+  const std::string& name() const { return m_name; }
+ private:
+  std::string m_name;
+ };
+
+ // dereferenced pointer
+ class PointeeStorage : public Storage
+ {
+ public:
+  PointeeStorage(const Data& pointer, const Data& offset): m_pointer(pointer), m_offset(offset) {
+   if (pointer.type() != DataType::Pointer)
+    throw std::runtime_error("Pointer argument must be a DataType::Pointer");
+   if (offset.type() != DataType::Size)
+    throw std::runtime_error("Offset argument must be a DataType::Size");
+  }
+  Data pointer() { return m_pointer; }
+  Data offset() { return m_offset; }
+ private:
+  Data m_pointer;
+  Data m_offset;
+ };
+
+}
diff --git a/test-asm.cpp b/tests/test-asm.cpp
index 2d3afa0..2d3afa0 100644
--- a/test-asm.cpp
+++ b/tests/test-asm.cpp
diff --git a/test-cpp.cpp b/tests/test-cpp.cpp
index 513a3a5..513a3a5 100644
--- a/test-cpp.cpp
+++ b/tests/test-cpp.cpp
diff --git a/test-cppbnf.cpp b/tests/test-cppbnf.cpp
index e365574..e365574 100644
--- a/test-cppbnf.cpp
+++ b/tests/test-cppbnf.cpp
diff --git a/test-elf.cpp b/tests/test-elf.cpp
index 0bf1d42..0bf1d42 100644
--- a/test-elf.cpp
+++ b/tests/test-elf.cpp
diff --git a/tests/test-flowgraph.cpp b/tests/test-flowgraph.cpp
new file mode 100644
index 0000000..132af4b
--- /dev/null
+++ b/tests/test-flowgraph.cpp
@@ -0,0 +1,50 @@
+#include "flowgraph/data.h"
+#include "flowgraph/graph.h"
+#include "flowgraph/node.h"
+#include "flowgraph/storage.h"
+
+#include <boost/algorithm/string.hpp>
+
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+#include <algorithm>
+#include <cctype>
+#include <deque>
+#include <map>
+#include <memory>
+#include <string>
+#include <system_error>
+#include <utility>
+#include <vector>
+
+using namespace std::string_literals;
+namespace fs = std::filesystem;
+
+using namespace FlowGraph;
+
+class FlowGraphTest: public ::testing::Test
+{
+protected:
+ FlowGraphTest() {
+  //debug = true;
+ }
+ ~FlowGraphTest() {
+ }
+ void SetUp(){
+ }
+ void TearDown(){
+ }
+};
+
+TEST_F(FlowGraphTest, build_graph) {
+ Graph graph;
+
+ Data pointer{ MakeLocalPointer("malloc1") };
+ Data size{ MakeLocalSize("size1") };
+ std::shared_ptr<Node> malloc1 {std::make_shared<AllocateDynamic>(pointer, size) };
+ std::shared_ptr<Node> free1{ std::make_shared<DeallocateDynamic>(pointer) };
+
+ graph.push_back(malloc1);
+ graph.push_back(free1);
+}
diff --git a/test-grammer.cpp b/tests/test-grammer.cpp
index 1734da2..1734da2 100644
--- a/test-grammer.cpp
+++ b/tests/test-grammer.cpp
diff --git a/test-lexer.cpp b/tests/test-lexer.cpp
index 23983f1..23983f1 100644
--- a/test-lexer.cpp
+++ b/tests/test-lexer.cpp
diff --git a/test-minicc.cpp b/tests/test-minicc.cpp
index baf8b3f..baf8b3f 100644
--- a/test-minicc.cpp
+++ b/tests/test-minicc.cpp