program.cc 7.6 KB
Newer Older
phlo's avatar
phlo committed
1 2
#include "program.hh"

phlo's avatar
phlo committed
3 4
#include <sstream>

phlo's avatar
phlo committed
5
#include "instruction.hh"
phlo's avatar
phlo committed
6 7
#include "parser.hh"

phlo's avatar
phlo committed
8 9
namespace ConcuBinE {

phlo's avatar
phlo committed
10 11 12
//==============================================================================
// macros
//==============================================================================
13

14 15 16 17
#define PARSER_ERROR(msg) do { parser_error(path, line_num, msg); } while (0)
#define INSTRUCTION_ERROR(msg) PARSER_ERROR("'" + symbol + "' " + msg)
#define UNKNOWN_INSTRUCTION_ERROR() INSTRUCTION_ERROR("unknown instruction")

phlo's avatar
phlo committed
18 19 20 21 22
//==============================================================================
// Program
//==============================================================================

//------------------------------------------------------------------------------
phlo's avatar
phlo committed
23
// public constructors
phlo's avatar
phlo committed
24 25
//------------------------------------------------------------------------------

phlo's avatar
phlo committed
26
Program::Program (std::istream & is, const std::string & p) : path(p)
phlo's avatar
phlo committed
27
{
phlo's avatar
phlo committed
28
  // list of jump instructions at pc referencing a certain label
phlo's avatar
phlo committed
29
  std::vector<std::pair<word_t, std::string>> labelled_jumps;
phlo's avatar
phlo committed
30

phlo's avatar
phlo committed
31 32
  size_t line_num = 1;
  for (std::string line_buf, token; std::getline(is, line_buf); line_num++)
phlo's avatar
phlo committed
33
    {
phlo's avatar
phlo committed
34
      // skip empty lines
phlo's avatar
phlo committed
35 36 37
      if (line_buf.empty())
        continue;

phlo's avatar
phlo committed
38
      std::istringstream line(line_buf);
phlo's avatar
phlo committed
39

phlo's avatar
phlo committed
40
      // skip comments
phlo's avatar
phlo committed
41 42 43
      if (line >> token && token.front() == '#')
        continue;

phlo's avatar
phlo committed
44
      // found label?
phlo's avatar
phlo committed
45 46
      else if (token.back() == ':')
        {
47 48
          const word_t pc = size();
          const std::string label = token.substr(0, token.size() - 1);
phlo's avatar
phlo committed
49

phlo's avatar
phlo committed
50
          // store label and the pc it was defined
51 52
          label_to_pc[label] = pc;
          pc_to_label[pc] = label;
phlo's avatar
phlo committed
53

phlo's avatar
phlo committed
54
          // read labelled command
phlo's avatar
phlo committed
55 56
          if (!(line >> token))
            PARSER_ERROR("missing instruction");
phlo's avatar
phlo committed
57 58
        }

phlo's avatar
phlo committed
59 60
      Instruction op;
      std::string symbol(std::move(token));
61 62

      if (line.eof())
phlo's avatar
phlo committed
63
        {
phlo's avatar
phlo committed
64
          try { op = Instruction::create(symbol); }
65 66 67 68
          catch (...) { UNKNOWN_INSTRUCTION_ERROR(); }
        }
      else
        {
phlo's avatar
phlo committed
69
          word_t arg;
70

phlo's avatar
phlo committed
71
          // try to parse the argument
72
          if (line >> arg)
phlo's avatar
phlo committed
73
            {
phlo's avatar
phlo committed
74
              try { op = Instruction::create(symbol, arg); }
75
              catch (...) { UNKNOWN_INSTRUCTION_ERROR(); }
phlo's avatar
phlo committed
76
            }
phlo's avatar
phlo committed
77
          // label or indirect addressing
78
          else
phlo's avatar
phlo committed
79
            {
phlo's avatar
phlo committed
80
              // clear failbit - recover ifstream
81
              line.clear();
phlo's avatar
phlo committed
82

phlo's avatar
phlo committed
83
              // discard leading whitespaces for later use of peek
phlo's avatar
phlo committed
84
              line >> std::ws;
85

phlo's avatar
phlo committed
86
              // arg is an indirect memory address
87
              if (line.peek() == '[')
phlo's avatar
phlo committed
88
                {
phlo's avatar
phlo committed
89
                  // parse enclosed address
90 91
                  line >> token;

phlo's avatar
phlo committed
92
                  try { arg = stoul(token.substr(1, token.size() - 2)); }
phlo's avatar
phlo committed
93
                  catch (std::invalid_argument & e)
94 95 96 97 98
                    {
                      PARSER_ERROR(
                        "indirect addressing does not support labels");
                    }

phlo's avatar
phlo committed
99
                  try { op = Instruction::create(symbol, arg); }
100 101
                  catch (...) { UNKNOWN_INSTRUCTION_ERROR(); }

phlo's avatar
phlo committed
102
                  // check if the instruction supports indirect addresses
phlo's avatar
phlo committed
103
                  if (!op.is_memory())
104
                    INSTRUCTION_ERROR("does not support indirect addressing");
phlo's avatar
phlo committed
105 106

                  op.indirect(true);
phlo's avatar
phlo committed
107
                }
phlo's avatar
phlo committed
108
              // arg is a label
phlo's avatar
phlo committed
109 110
              else
                {
phlo's avatar
phlo committed
111 112
                  // create dummy Instruction
                  try { op = Instruction::create(symbol, word_max); }
113
                  catch (...) { UNKNOWN_INSTRUCTION_ERROR(); }
phlo's avatar
phlo committed
114

phlo's avatar
phlo committed
115
                  // check if the instruction supports labels (is a jmp)
phlo's avatar
phlo committed
116 117
                  if (!op.is_jump())
                    INSTRUCTION_ERROR("does not support labels");
phlo's avatar
phlo committed
118

phlo's avatar
phlo committed
119 120
                  if (!(line >> token))
                    PARSER_ERROR("missing label");
121

phlo's avatar
phlo committed
122 123
                  // add to the list of labelled jumps
                  labelled_jumps.push_back(make_pair(size(), token));
phlo's avatar
phlo committed
124 125 126 127
                }
            }
        }

phlo's avatar
phlo committed
128
      push_back(std::move(op));
phlo's avatar
phlo committed
129 130
    }

phlo's avatar
phlo committed
131 132
  // update labelled instruction's argument
  for (const auto & [pc, label] : labelled_jumps)
phlo's avatar
phlo committed
133 134
    try
      {
phlo's avatar
phlo committed
135
        (*this)[pc].arg(label_to_pc.at(label));
phlo's avatar
phlo committed
136 137 138
      }
    catch (...)
      {
phlo's avatar
phlo committed
139
        throw std::runtime_error(path + ": unknown label [" + label + "]");
phlo's avatar
phlo committed
140 141
      }

phlo's avatar
phlo committed
142 143 144 145 146 147 148 149 150 151 152
  // find illegal jumps
  for (word_t pc = 0; pc < size(); pc++)
    {
      const auto & op = (*this)[pc];

      if (op.is_jump() && op.arg() >= size())
        throw
          std::runtime_error(
            path + ": illegal jump [" + std::to_string(pc) + "]");
    }

phlo's avatar
phlo committed
153 154 155
  // insert final HALT (if missing)
  if (!(back().type() & Instruction::Type::control))
    push_back(Instruction::create("HALT"));
phlo's avatar
phlo committed
156 157 158 159 160 161 162 163 164 165 166
}

//------------------------------------------------------------------------------
// public member functions
//------------------------------------------------------------------------------

// Program::predecessors -------------------------------------------------------

std::unordered_map<word_t, std::set<word_t>> Program::predecessors () const
{
  std::unordered_map<word_t, std::set<word_t>> predecessors;
phlo's avatar
phlo committed
167

phlo's avatar
phlo committed
168
  // collect predecessors
phlo's avatar
phlo committed
169
  for (word_t pc = 0, final = size() - 1; pc <= final; pc++)
phlo's avatar
phlo committed
170
    {
phlo's avatar
phlo committed
171
      const Instruction & op = (*this)[pc];
phlo's avatar
phlo committed
172

phlo's avatar
phlo committed
173
      if (op.is_jump())
174
        {
phlo's avatar
phlo committed
175
          if (&op.symbol() != &Instruction::Jmp::symbol)
phlo's avatar
phlo committed
176 177
            predecessors[pc + 1].insert(pc);

phlo's avatar
phlo committed
178
          predecessors[op.arg()].insert(pc);
179
        }
phlo's avatar
phlo committed
180
      else if (pc < final)
phlo's avatar
phlo committed
181 182 183 184 185
        {
          using Halt = Instruction::Halt;
          using Exit = Instruction::Exit;

          if (&op.symbol() != &Exit::symbol && &op.symbol() != &Halt::symbol)
phlo's avatar
phlo committed
186
            predecessors[pc + 1].insert(pc);
phlo's avatar
phlo committed
187
        }
phlo's avatar
phlo committed
188
    }
phlo's avatar
phlo committed
189

phlo's avatar
phlo committed
190
  // check for unreachable instructions
phlo's avatar
phlo committed
191 192
  for (word_t pc = 1; pc < size(); pc++)
    if (predecessors.find(pc) == predecessors.end())
phlo's avatar
phlo committed
193 194 195
      throw
        std::runtime_error(
          path + ": unreachable instruction [" + std::to_string(pc) + "]");
phlo's avatar
phlo committed
196

phlo's avatar
phlo committed
197
  return predecessors;
phlo's avatar
phlo committed
198 199
}

phlo's avatar
phlo committed
200
// Program::pc -----------------------------------------------------------------
phlo's avatar
phlo committed
201

phlo's avatar
phlo committed
202
word_t Program::pc (const std::string & label) const
phlo's avatar
phlo committed
203
{
204
  const auto it = label_to_pc.find(label);
phlo's avatar
phlo committed
205

206
  if (it == label_to_pc.end())
phlo's avatar
phlo committed
207
    throw std::runtime_error(path + ": unknown label [" + label + "]");
phlo's avatar
phlo committed
208

209
  return it->second;
phlo's avatar
phlo committed
210 211
}

phlo's avatar
phlo committed
212
// Program::label --------------------------------------------------------------
phlo's avatar
phlo committed
213

phlo's avatar
phlo committed
214
std::string Program::label (const word_t pc) const
phlo's avatar
phlo committed
215 216 217 218
{
  const auto it = pc_to_label.find(pc);

  if (it == pc_to_label.end())
phlo's avatar
phlo committed
219
    throw
phlo's avatar
phlo committed
220
      std::runtime_error(path + ": no label for [" + std::to_string(pc) + "]");
phlo's avatar
phlo committed
221

222
  return it->second;
phlo's avatar
phlo committed
223 224
}

phlo's avatar
phlo committed
225 226
// Program::print --------------------------------------------------------------

phlo's avatar
phlo committed
227
std::string Program::print () const
228
{
phlo's avatar
phlo committed
229
  std::ostringstream ss;
phlo's avatar
phlo committed
230

phlo's avatar
phlo committed
231
  for (word_t i = 0; i < size(); i++)
phlo's avatar
phlo committed
232
    ss <<  print(i) << eol;
phlo's avatar
phlo committed
233 234

  return ss.str();
235 236
}

phlo's avatar
phlo committed
237
std::string Program::print (const word_t pc) const
238
{
phlo's avatar
phlo committed
239
  std::ostringstream ss;
phlo's avatar
phlo committed
240

phlo's avatar
phlo committed
241
  // check if instruction is referenced by a label
242 243
  auto label_it = pc_to_label.find(pc);
  if (label_it != pc_to_label.end())
244
    ss << label_it->second << ": ";
245

phlo's avatar
phlo committed
246 247
  // instruction symbol
  const Instruction & op = (*this)[pc];
248

249
  ss << op.symbol();
phlo's avatar
phlo committed
250 251 252

  // print unary instruction's argument
  if (op.is_unary())
253
    {
phlo's avatar
phlo committed
254
      ss << ' ';
255

phlo's avatar
phlo committed
256 257 258
      label_it = pc_to_label.find(op.arg());
      if (op.is_jump() && label_it != pc_to_label.end())
        {
259
          ss << label_it->second;
phlo's avatar
phlo committed
260 261 262
        }
      else if (op.is_memory())
        {
phlo's avatar
phlo committed
263 264
          if (op.indirect())
            ss << "[" << op.arg() << "]";
phlo's avatar
phlo committed
265
          else
phlo's avatar
phlo committed
266
            ss << op.arg();
phlo's avatar
phlo committed
267
        }
268
      else
phlo's avatar
phlo committed
269 270 271
        {
          ss << op.arg();
        }
272
    }
phlo's avatar
phlo committed
273 274

  return ss.str();
275
}
276

phlo's avatar
phlo committed
277
} // namespace ConcuBinE