[taf] Design and implement TAF IR

[vityaman]

TAF Disign

Types

class Kind(ABC):
  pass

class Int(Kind): 
  """Integer 64 bits."""
  pass

class Bool(Kind): 
  """True or False"""
  pass

class Signature(Kind):
  """(*params) -> value"""
  params: list[Type]
  value: Type

Constructs

class Symbol:
  """
  Such ['v0', 'v1', 'v2', 'v5', 'v4', 'c0', '2', '5'] in listing:
    v0: int = load(5: int): int         
    v1: int = load(2: int): int         
    v2: int = div(v0: int, v1: int): int
    v5: int = call(c0: (int) -> int, v4: int): int
  """
  unique_name: str
  kind: Kind

class Memory(Symbol):
  """Created during `tafka` Program to TAF transformation."""
  pass

class Register(Symbol):
  """Replaces `Temporary` during `regal` register allocation pass."""
  pass

RValue

class RValue(ABC):
  pass

class Intrinsic(RValue):
  name: str

  @property
  signature: Signature

class UnaryOperator(Intrinsic):
  argument: Symbol

class Copy (UnaryOperator): pass
class Neg  (UnaryOperator): pass
class Load (UnaryOperator): pass
class Store(UnaryOperator): pass

class BinaryOperator(Intrinsic):
  left: Symbol
  right: Symbol

class Sum(BinaryOperator): pass
class Mul(BinaryOperator): pass
class Div(BinaryOperator): pass
class Rem(BinaryOperator): pass

class Invocation(RValue):
  procedure: Symbol
  args: list[Symbol]

Basic Block & Statements

class Label:
  name: str

class Statement(ABC):
  pass

class Block:
  label: Label
  statements: list[Statement]

  @property
  def last(self) -> Transfer:
    return statements[-1]

class Assignment(Statement):
  target: Symbol
  source: RValue

class Transfer(Statement):
  pass

class Goto(Transfer):
  block: Block

class Conditional(Transfer):
  condition: Symbol
  then_branch: Block
  else_branch: Block

  @property
  end: Block

class Return(Transfer):
  value: Symbol

Top level

class TopLevel(ABC):
  pass

class Procedure(TopLevel):
  symbol: Symbol  # symbol.kind is always a Signature
  params: list[str]
  entry: Block

  @property
  signature: Signature

  @property
  parameters: list[Symbol]

Reference

[vityaman]

Example: Basic arithmetic

Input:

(sum (div 5 2) (rem (sum 2 2) 2))

Output:

procedure __start__():
  v0: int  = load(5: int): int          // 5
  v1: int  = load(2: int): int          // 2
  v2: int  = div(v0: int, v1: int): int // (div 5 2)
  v3: int  = load(2: int): int          // 2
  v4: int  = load(2: int): int          // 2
  v5: int  = sum(v3: int, v4: int): int // (sum 2 2)
  v6: int  = load(2: int): int          // 2
  v7: int  = rem(v5: int, v6: int): int // (rem (sum 2 2) 2)
  v8: int  = sum(v2: int, v7: int): int // (sum ... ...)
  res: int = r8: int

[vityaman]

Example: Control Flow

Input:

(sum 
  (if (eq (sum 2 3) 5) 
    (1) 
    (rem 2 2)) 
  (if (lt 2 3) 
    (mul 1 1)
    (0)))

Output:

procedure __start__():
  v0: int  = int(2): int                    // 2
  v1: int  = int(3): int                    // 3
  v2: int  = sum(v0: int, v1: int): int     // (sum 2 3)
  v3: int  = int(5): int                    // 5
  v4: bool = eq(v2: int, v3: int): bool     // (eq (sum 2 3) 5)

  if v4 then l0_then else l1_else end l2_end
  l0_then:
    v5: int = int(1): int                   // 1
    v6: int = v5: int                       // then result
    goto l2_end
  l1_else:
    v7: int = int(2): int                   // 2
    v8: int = int(2): int                   // 2
    v9: int = rem(v7: int, v7: int): int    // (rem 2 2)
    v6: int = v9: int                       // else result
  l2_end:
  v6: int = v6: int

  v10: int  = int(2): int
  v11: int  = int(3): int
  v12: bool = lt(v10: int, v11: int): bool

  if v12 then l3_then else l4_else end l5_end
  l3_then:
    v13: int = int(1): int
    v14: int = int(1): int
    v15: int = mul(v13: int, v14: int): int
    v16: int = v15: int
    goto l5_end
  l4_else:
    v17: int = int(0): int
    v16: int = v17: int
  l5_end:
  v16: int = v16: int

  v19: int = sum(v6: int, v16: int): int
  res: int = v19: int

[vityaman]

Example: Variable definition.

Input:

(def a (sum 2 2))
(def b (rem a 5))
(sum a b)

Output (greedy):

procedure __start__():
  v0: int = load(0: int): int          // (def a ...)
  v1: int = load(2: int): int          // 2
  v2: int = load(2: int): int          // 2
  v3: int = sum(v0: int, v1: int): int // (sum 2 2)
  v0: int = v3: int                    // (def a (sum 2 2)), or just omit it

  v4: int = load(0: int): int          // (def b ...)
  v5: int = v0: int                    // ask to give `v{i}` for `a`
  v6: int = load(5: int): int          // 5
  v7: int = rem(v5: int, v6: int): int // (rem a 5)
  v4: int = v7: int                    // (def b (rem a 5)), or just omit it

  v8:  int = v0: int                     // a
  v9:  int = v4: int                     // b
  v10: int = sum(v8: int, v9: int): int // (sum a b)

  res: int = v10: int

[vityaman]

Example: Simple procedure definition and usage

Input:

(def inc (lambda (x int) (sum x +1)))
(inc (inc 5))

Output:

procedure c0 (v0: int): int:
  v1: int = load(1: int): int
  v2: int = sum(v0: int, v1: int): int
  return v2: int

procedure __start__(): int:
  v3:  int = load(5: int): int
  v4:  int = call(c0: (int) -> int, v3: int): int
  v5:  int = call(c0: (int) -> int, v4: int): int
  res: int = v5: int
  ret: int = load(0: int): int
  return ret: int

[vityaman]

TODO: add store instruction UPD: Done