B06902021 吳聖福 B07902024 塗大為 Compile: $ make (use `-j` for parallel compilation) * Note that our execution & compilation environment is `linux1` workstation instead of the given VM, since we need to use a new version of g++/bison/flex. (There are `riscv64-linux-gnu-*` cross-compiler on workstations now.) Usage: $ ./parser -o [output=output.s] [file] [-O] * Use `-O` to turn on optimization (including register allocation & frequency analysis) Notes: * We use an external library `argparse` (https://github.com/p-ranav/argparse) to parse the command line arguments. New features: * Fix operator precedence * Allow expression lists in `if`, `while`, `return` * Allow long distance jumps in branch instructions (GCC and Clang both fail on the testcase generated by `testcase/gen-large-if.cpp`) * Register lifetime analysis: We analyze the read-write pattern in each basic block, and run a DFS to determine the lifetime (indicated by an interval) of each pseudo register. The complexity is O(# of basic blocks * # of pseudo registers) * Register allocation: Since the lifetime of each pseudo register is an interval, register allocation becomes an interval scheduling or interval partition problem, which can be done in O(n log n). Moreover, one can easily utilize caller-saved registers by allocating the psuedo registers whose lifetime does not intersect with any function calls to caller-saved registers. * Register frequency analysis: Pseudo registers that appear more frequently have higher priorities to be placed in the real registers.