MXVM 1.8.1
Virtual Machine, Compiler, and Pascal Frontend
Loading...
Searching...
No Matches
icode_opt.cpp
Go to the documentation of this file.
1
6#include "mxvm/icode.hpp"
7#include <regex>
8#include <sstream>
9#include <string>
10#include <unordered_map>
11#include <unordered_set>
12#include <vector>
13
14namespace mxvm {
15
16 static std::string join_lines(const std::vector<std::string> &v) {
17 std::ostringstream os;
18 for (size_t i = 0; i < v.size(); ++i) {
19 os << v[i];
20 if (i + 1 < v.size())
21 os << '\n';
22 }
23 return os.str();
24 }
25
26 /*static inline std::string trim(std::string s) {
27 auto issp = [](int c){ return std::isspace(c); };
28 while (!s.empty() && issp(s.front())) s.erase(s.begin());
29 while (!s.empty() && issp(s.back())) s.pop_back();
30 return s;
31 }*/
32
33 static bool is_label(const std::string &line) {
34 static const std::regex re_label(R"(^\s*(?:[A-Za-z_.$][\w.$]*|\d+)\s*:)");
35 return std::regex_search(line, re_label);
36 }
37
38 static std::vector<std::string> opt_core_lines(const std::vector<std::string> &lines) {
39 std::regex re_mov_reg(R"(^\s*mov[bwlq]?\s+(%[a-z0-9]+)\s*,\s*(%[a-z0-9]+)\s*(?:[#;].*)?$)", std::regex::icase);
40 std::regex re_mem_to_reg(R"(^\s*mov[bwlq]?\s+([A-Za-z0-9_]+(?:\‍(%rip\))?)\s*,\s*(%[a-z0-9]+)\s*(?:[#;].*)?$)", std::regex::icase);
41 std::regex re_reg_to_mem(R"(^\s*mov[bwlq]?\s+(%[a-z0-9]+)\s*,\s*([A-Za-z0-9_]+(?:\‍(%rip\))?)\s*(?:[#;].*)?$)", std::regex::icase);
42 std::regex re_modifies_reg(R"(^\s*(?:add|sub|mul|imul|div|idiv|and|or|xor|shl|shr|sal|sar|not|neg)[a-z]*\s+.*,\s*(%[a-z0-9]+)\s*(?:[#;].*)?$)", std::regex::icase);
43 std::regex re_call_or_jmp(R"(^\s*(?:call|jmp|je|jne|jz|jnz|jg|jge|jl|jle|ja|jae|jb|jbe)[a-z]*\s+)", std::regex::icase);
44 std::regex re_xor_eax(R"(^\s*xorq?\s+%eax\s*,\s*%eax\s*(?:[#;].*)?$)", std::regex::icase);
45 std::regex re_call_func(R"(^\s*call\s+([_A-Za-z][_A-Za-z0-9]*)\s*(?:[#;].*)?$)", std::regex::icase);
46 static const std::unordered_set<std::string> variadic_funcs = {
47 "printf", "fprintf", "sprintf", "snprintf", "scanf", "fscanf", "sscanf",
48 "vprintf", "vfprintf", "vsprintf", "vsnprintf", "vscanf", "vfscanf", "vsscanf"};
49 std::vector<std::string> out;
50 out.reserve(lines.size());
51 struct ValueInfo {
52 std::string location;
53 bool valid = true;
54 };
55 std::unordered_map<std::string, ValueInfo> reg_contents;
56 std::unordered_map<std::string, ValueInfo> mem_contents;
57 auto invalidate_tracking = [&]() {
58 reg_contents.clear();
59 mem_contents.clear();
60 };
61 auto clobber_reg = [&](const std::string &reg) {
62 reg_contents.erase(reg);
63 for (auto it = mem_contents.begin(); it != mem_contents.end();) {
64 if (it->second.location == reg)
65 it = mem_contents.erase(it);
66 else
67 ++it;
68 }
69 };
70 for (size_t i = 0; i < lines.size(); ++i) {
71 const std::string &line = lines[i];
72
73 if (std::regex_match(line, re_xor_eax) && (i + 1 < lines.size())) {
74 std::smatch m;
75 if (std::regex_match(lines[i + 1], m, re_call_func)) {
76 std::string func_name = m[1].str();
77 if (variadic_funcs.find(func_name) == variadic_funcs.end()) {
78 continue;
79 }
80 }
81 }
82 if (is_label(line) || std::regex_search(line, re_call_or_jmp)) {
83 out.push_back(line);
84 invalidate_tracking();
85 continue;
86 }
87
88 {
89 std::smatch m;
90 if (std::regex_match(line, m, re_modifies_reg)) {
91 clobber_reg(m[1].str());
92 out.push_back(line);
93 continue;
94 }
95 }
96
97 {
98 std::smatch m;
99 if (std::regex_match(line, m, re_mem_to_reg)) {
100 const std::string mem = m[1].str();
101 const std::string reg = m[2].str();
102
103 clobber_reg(reg);
104
105 auto it = mem_contents.find(mem);
106 if (it != mem_contents.end() && it->second.valid) {
107 const std::string &src_reg = it->second.location;
108 if (src_reg != reg)
109 out.push_back("\tmovq " + src_reg + ", " + reg);
110 reg_contents[reg] = {mem, true};
111 continue;
112 }
113
114 out.push_back(line);
115 reg_contents[reg] = {mem, true};
116 continue;
117 }
118 }
119
120 {
121 std::smatch m;
122 if (std::regex_match(line, m, re_reg_to_mem)) {
123 const std::string reg = m[1].str();
124 const std::string mem = m[2].str();
125 mem_contents[mem] = {reg, true};
126 out.push_back(line);
127 continue;
128 }
129 }
130
131 {
132 std::smatch m;
133 if (std::regex_match(line, m, re_mov_reg)) {
134 const std::string src = m[1].str();
135 const std::string dst = m[2].str();
136 if (src == dst)
137 continue;
138
139 clobber_reg(dst);
140
141 auto it_src = reg_contents.find(src);
142 if (it_src != reg_contents.end())
143 reg_contents[dst] = it_src->second;
144 else
145 reg_contents[dst] = {src, true};
146
147 out.push_back(line);
148 continue;
149 }
150 }
151
152 invalidate_tracking();
153 out.push_back(line);
154 }
155
156 return out;
157 }
158
159 static std::vector<std::string> x64_opt_core_lines(const std::vector<std::string> &lines) {
160 std::regex re_mov_reg(R"(^\s*movq?\s+(%[a-z0-9]+)\s*,\s*(%[a-z0-9]+)\s*(?:[#;].*)?$)", std::regex::icase);
161 std::regex re_mem_to_reg(R"(^\s*movq?\s+([A-Za-z0-9_]+(?:\‍(%rip\))?)\s*,\s*(%[a-z0-9]+)\s*(?:[#;].*)?$)", std::regex::icase);
162 std::regex re_reg_to_mem(R"(^\s*movq?\s+(%[a-z0-9]+)\s*,\s*([A-Za-z0-9_]+(?:\‍(%rip\))?)\s*(?:[#;].*)?$)", std::regex::icase);
163 std::regex re_modifies_reg(R"(^\s*(?:add|sub|mul|imul|div|idiv|and|or|xor|shl|shr|sal|sar|not|neg)[a-z]*\s+.*,\s*(%[a-z0-9]+)\s*(?:[#;].*)?$)", std::regex::icase);
164 std::regex re_call_or_jmp(R"(^\s*(?:call|jmp|je|jne|jz|jnz|jg|jge|jl|jle|ja|jae|jb|jbe)[a-z]*\s+)", std::regex::icase);
165
166 std::regex re_xor_eax(R"(^\s*xorq?\s+%eax\s*,\s*%eax\s*(?:[#;].*)?$)", std::regex::icase);
167 std::regex re_call_func(R"(^\s*call\s+([_A-Za-z][_A-ZaZ0-9]*)\s*(?:[#;].*)?$)", std::regex::icase);
168 static const std::unordered_set<std::string> variadic_funcs = {
169 "printf", "fprintf", "sprintf", "snprintf", "scanf", "fscanf", "sscanf",
170 "vprintf", "vfprintf", "vsprintf", "vsnprintf", "vscanf", "vfscanf", "vsscanf"};
171 auto local_is_label = [](const std::string &s) {
172 static const std::regex re(R"(^\s*(?:[A-Za-z_.$][\w.$]*|\d+)\s*:)");
173 return std::regex_search(s, re);
174 };
175 auto has_call_or_ret = [](const std::string &s) {
176 return s.find(" call ") != std::string::npos ||
177 s.find("\tcall ") != std::string::npos ||
178 s.find(" ret") != std::string::npos ||
179 s.find("\tret") != std::string::npos;
180 };
181 auto touches_rsp = [](const std::string &s) {
182 return s.find("%rsp") != std::string::npos || s.find("(%rsp") != std::string::npos;
183 };
184
185 std::vector<std::string> out;
186 out.reserve(lines.size());
187 std::vector<int> frame_bytes;
188
189 std::regex re_sub_rsp(R"(^\s*sub\s+\$([0-9]+)\s*,\s*%rsp\s*(?:[#;].*)?$)", std::regex::icase);
190 std::regex re_add_rsp(R"(^\s*add\s+\$([0-9]+)\s*,\s*%rsp\s*(?:[#;].*)?$)", std::regex::icase);
191
192 struct ValueInfo {
193 std::string location;
194 bool valid = true;
195 };
196 std::unordered_map<std::string, ValueInfo> reg_contents;
197 std::unordered_map<std::string, ValueInfo> mem_contents;
198
199 auto invalidate_tracking = [&]() {
200 reg_contents.clear();
201 mem_contents.clear();
202 };
203
204 auto clobber_reg = [&](const std::string &reg) {
205 reg_contents.erase(reg);
206 for (auto it = mem_contents.begin(); it != mem_contents.end();) {
207 if (it->second.location == reg)
208 it = mem_contents.erase(it);
209 else
210 ++it;
211 }
212 };
213
214 for (size_t i = 0; i < lines.size(); ++i) {
215 const std::string &line = lines[i];
216
217 if (std::regex_match(line, re_xor_eax) && (i + 1 < lines.size())) {
218 std::smatch m;
219 if (std::regex_match(lines[i + 1], m, re_call_func)) {
220 std::string func_name = m[1].str();
221 if (!func_name.empty() && func_name[0] == '_') {
222 func_name = func_name.substr(1);
223 }
224 if (variadic_funcs.find(func_name) == variadic_funcs.end()) {
225 continue;
226 }
227 }
228 }
229 if (local_is_label(line)) {
230 out.push_back(line);
231 invalidate_tracking();
232 continue;
233 }
234 {
235 std::smatch m;
236 if (std::regex_match(line, m, re_sub_rsp)) {
237 frame_bytes.push_back(std::stoi(m[1].str()));
238 out.push_back(line);
239 continue;
240 }
241 }
242 if (!frame_bytes.empty()) {
243 out.push_back(line);
244 std::smatch m;
245 if (std::regex_match(line, m, re_add_rsp)) {
246 int n = std::stoi(m[1].str());
247 if (!frame_bytes.empty() && frame_bytes.back() == n)
248 frame_bytes.pop_back();
249 }
250 continue;
251 }
252 if (has_call_or_ret(line) || touches_rsp(line) || std::regex_search(line, re_call_or_jmp)) {
253 out.push_back(line);
254 invalidate_tracking();
255 continue;
256 }
257
258 {
259 std::smatch m;
260 if (std::regex_match(line, m, re_modifies_reg)) {
261 clobber_reg(m[1].str());
262 out.push_back(line);
263 continue;
264 }
265 }
266
267 {
268 std::smatch m;
269 if (std::regex_match(line, m, re_reg_to_mem)) {
270 const std::string reg = m[1].str();
271 const std::string mem = m[2].str();
272 mem_contents[mem] = {reg, true};
273 out.push_back(line);
274 continue;
275 }
276 }
277
278 {
279 std::smatch m;
280 if (std::regex_match(line, m, re_mov_reg)) {
281 const std::string src = m[1].str();
282 const std::string dst = m[2].str();
283 if (src == dst)
284 continue;
285
286 clobber_reg(dst);
287
288 auto it_src = reg_contents.find(src);
289 if (it_src != reg_contents.end())
290 reg_contents[dst] = it_src->second;
291 else
292 reg_contents[dst] = {src, true};
293
294 out.push_back(line);
295 continue;
296 }
297 }
298
299 {
300 std::smatch m;
301 if (std::regex_match(line, m, re_mem_to_reg)) {
302 const std::string mem = m[1].str();
303 const std::string reg = m[2].str();
304
305 clobber_reg(reg);
306
307 auto it = mem_contents.find(mem);
308 if (it != mem_contents.end() && it->second.valid) {
309 const std::string &src_reg = it->second.location;
310 if (src_reg != reg)
311 out.push_back("\tmovq " + src_reg + ", " + reg);
312 reg_contents[reg] = {mem, true};
313 continue;
314 }
315
316 out.push_back(line);
317 reg_contents[reg] = {mem, true};
318 continue;
319 }
320 }
321
322 invalidate_tracking();
323 out.push_back(line);
324 }
325
326 return out;
327 }
328
329 static std::string darwin_prefix_calls(const std::string &line,
330 const std::unordered_set<std::string> &macos_functions) {
331 static const std::regex re_call(R"(\b(call|jmp)\s+([_A-Za-z][_A-Za-z0-9]*)\b)");
332 std::string result;
333 result.reserve(line.size() + 16);
334
335 size_t last = 0;
336 for (std::sregex_iterator it(line.begin(), line.end(), re_call), end; it != end; ++it) {
337 const auto &m = *it;
338 const auto pos = static_cast<size_t>(m.position());
339 const auto len = static_cast<size_t>(m.length());
340 const std::string fn = m[2].str();
341
342 result.append(line, last, pos - last);
343
344 std::string piece = m.str();
345 if (fn == "main" || macos_functions.count(fn)) {
346 const auto fnpos = piece.rfind(fn);
347 if (fnpos != std::string::npos)
348 piece.replace(fnpos, fn.size(), "_" + fn);
349 }
350 result += piece;
351
352 last = pos + len;
353 }
354 result.append(line, last, std::string::npos);
355 return result;
356 }
357
358 static std::vector<std::string> opt_darwin_lines(const std::vector<std::string> &lines) {
359 std::vector<std::string> out;
360 out.reserve(lines.size());
361
362 std::regex re_stdin_access(R"(movq?\s+stdin\‍(%rip\)\s*,\s*(%\w+))", std::regex::icase);
363 std::regex re_stdout_access(R"(movq?\s+stdout\‍(%rip\)\s*,\s*(%\w+))", std::regex::icase);
364 std::regex re_stderr_access(R"(movq?\s+stderr\‍(%rip\)\s*,\s*(%\w+))", std::regex::icase);
365 std::regex re_global_main(R"(^\s*\.(?:global|globl)\s+main\s*$)");
366 std::regex re_main_label(R"(^\s*main\s*:\s*$)");
367 std::regex re_global_function(R"(^\s*\.(?:global|globl)\s+([_a-zA-Z][_a-zA-Z0-9]*)(?:\s|$))");
368 std::regex re_function_label(R"(^([_a-zA-Z][_a-zA-Z0-9]*)\s*:\s*$)");
369
370 std::unordered_set<std::string> macos_functions;
371
372 for (const auto &raw : lines) {
373 std::string line = raw;
374
375 if (std::regex_search(line, re_global_main)) {
376 out.push_back("\t.globl _main");
377 continue;
378 }
379 if (std::regex_search(line, re_main_label)) {
380 out.push_back("_main:");
381 continue;
382 }
383
384 std::smatch m_func;
385 if (std::regex_search(line, m_func, re_global_function)) {
386 std::string fn = m_func[1].str();
387 if (fn != "main") {
388 macos_functions.insert(fn);
389 out.push_back("\t.globl _" + fn);
390 }
391 continue;
392 }
393 if (std::regex_search(line, m_func, re_function_label)) {
394 std::string fn = m_func[1].str();
395 if (fn != "main" && macos_functions.count(fn)) {
396 out.push_back("_" + fn + ":");
397 } else {
398 out.push_back(line);
399 }
400 continue;
401 }
402
403 std::smatch m;
404 if (std::regex_search(line, m, re_stdin_access)) {
405 std::string r = m[1].str();
406 out.push_back("\tmovq ___stdinp@GOTPCREL(%rip), %rax");
407 out.push_back("\tmovq (%rax), " + r);
408 continue;
409 }
410 if (std::regex_search(line, m, re_stdout_access)) {
411 std::string r = m[1].str();
412 out.push_back("\tmovq ___stdoutp@GOTPCREL(%rip), %rax");
413 out.push_back("\tmovq (%rax), " + r);
414 continue;
415 }
416 if (std::regex_search(line, m, re_stderr_access)) {
417 std::string r = m[1].str();
418 out.push_back("\tmovq ___stderrp@GOTPCREL(%rip), %rax");
419 out.push_back("\tmovq (%rax), " + r);
420 continue;
421 }
422
423 std::regex re_single_stdout(R"(^\s*movq?\s+_stdout\‍(%rip\)\s*,\s*(%\w+)\s*(?:[#;].*)?$)", std::regex::icase);
424 if (std::regex_search(line, m, re_single_stdout)) {
425 std::string r = m[1].str();
426 out.push_back("\tmovq ___stdoutp@GOTPCREL(%rip), %rax");
427 out.push_back("\tmovq (%rax), " + r);
428 continue;
429 }
430 std::regex re_single_stderr(R"(^\s*movq?\s+_stderr\‍(%rip\)\s*,\s*(%\w+)\s*(?:[#;].*)?$)", std::regex::icase);
431 if (std::regex_search(line, m, re_single_stderr)) {
432 std::string r = m[1].str();
433 out.push_back("\tmovq ___stderrp@GOTPCREL(%rip), %rax");
434 out.push_back("\tmovq (%rax), " + r);
435 continue;
436 }
437 std::regex re_single_stdin(R"(^\s*movq?\s+_stdin\‍(%rip\)\s*,\s*(%\w+)\s*(?:[#;].*)?$)", std::regex::icase);
438 if (std::regex_search(line, m, re_single_stdin)) {
439 std::string r = m[1].str();
440 out.push_back("\tmovq ___stdinp@GOTPCREL(%rip), %rax");
441 out.push_back("\tmovq (%rax), " + r);
442 continue;
443 }
444
445 line = darwin_prefix_calls(line, macos_functions);
446 out.push_back(line);
447 }
448
449 return out;
450 }
451
452 static std::vector<std::string> opt_x64_windows_lines(const std::vector<std::string> &lines) {
453 static const std::regex add_rx(R"(^\s*addq?\s+\$([0-9]+|0x[0-9a-fA-F]+)\s*,\s*%rsp\s*(?:#.*)?$)");
454 static const std::regex sub_rx(R"(^\s*subq?\s+\$([0-9]+|0x[0-9a-fA-F]+)\s*,\s*%rsp\s*(?:#.*)?$)");
455
456 auto parse_imm = [](const std::string &s) -> unsigned long long {
457 return std::stoull(s, nullptr, 0);
458 };
459
460 std::vector<std::string> out;
461 out.reserve(lines.size());
462
463 for (size_t i = 0; i < lines.size();) {
464 const std::string &a = lines[i];
465
466 std::smatch ma, mb;
467 bool a_is_add = std::regex_match(a, ma, add_rx);
468 bool a_is_sub = !a_is_add && std::regex_match(a, ma, sub_rx);
469
470 if ((a_is_add || a_is_sub) && (i + 1) < lines.size()) {
471 const std::string &b = lines[i + 1];
472 bool b_is_add = std::regex_match(b, mb, add_rx);
473 bool b_is_sub = !b_is_add && std::regex_match(b, mb, sub_rx);
474
475 if ((a_is_add && b_is_sub) || (a_is_sub && b_is_add)) {
476 unsigned long long ia = parse_imm(ma[1].str());
477 unsigned long long ib = parse_imm(mb[1].str());
478 if (ia == ib) {
479 i += 2;
480 continue;
481 }
482 }
483 }
484
485 out.push_back(a);
486 ++i;
487 }
488
489 return out;
490 }
491
492 static std::vector<std::string> opt_linux_lines(const std::vector<std::string> &lines) {
493 return lines;
494 }
495
496 std::string Program::gen_optimize(const std::string &code, const Platform &platform_name) {
497 std::vector<std::string> lines;
498 {
499 std::istringstream stream(code);
500 std::string s;
501 while (std::getline(stream, s))
502 lines.push_back(s);
503 }
504
505 if (platform_name == Platform::WINX64) {
506 auto core = x64_opt_core_lines(lines);
507 auto win = opt_x64_windows_lines(core);
508 return join_lines(win);
509 } else {
510 auto core = opt_core_lines(lines);
511 auto os = (platform_name == Platform::DARWIN) ? opt_darwin_lines(core)
512 : opt_linux_lines(core);
513 return join_lines(os);
514 }
515 }
516} // namespace mxvm
mxvm::Program::gen_optimize
std::string gen_optimize(const std::string &code, const Platform &platform)
Peephole optimizer for generated assembly.
Definition icode_opt.cpp:496
pos
int64_t pos(const char *substr, const char *s)
Definition cstring.c:51
icode.hpp
Intermediate code representation, execution engine, and native x64 code generation (SysV + Win64).
mxvm
Definition ast.hpp:14
mxvm::darwin_prefix_calls
static std::string darwin_prefix_calls(const std::string &line, const std::unordered_set< std::string > &macos_functions)
Definition icode_opt.cpp:329
mxvm::opt_core_lines
static std::vector< std::string > opt_core_lines(const std::vector< std::string > &lines)
Definition icode_opt.cpp:38
mxvm::Platform
Platform
Target platform for native code generation.
Definition parser.hpp:42
mxvm::is_label
static bool is_label(const std::string &line)
Definition icode_opt.cpp:33
mxvm::opt_linux_lines
static std::vector< std::string > opt_linux_lines(const std::vector< std::string > &lines)
Definition icode_opt.cpp:492
mxvm::join_lines
static std::string join_lines(const std::vector< std::string > &v)
Definition icode_opt.cpp:16
mxvm::opt_x64_windows_lines
static std::vector< std::string > opt_x64_windows_lines(const std::vector< std::string > &lines)
Definition icode_opt.cpp:452
mxvm::opt_darwin_lines
static std::vector< std::string > opt_darwin_lines(const std::vector< std::string > &lines)
Definition icode_opt.cpp:358
mxvm::x64_opt_core_lines
static std::vector< std::string > x64_opt_core_lines(const std::vector< std::string > &lines)
Definition icode_opt.cpp:159