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.