*************************************************************
* Variable-Assignment-Model (VAM) -- Structure and Language *
*************************************************************

Created: 2012-01-24

Content
=======

1. Data-flow structure
2. Storage nodes
3. Functional nodes
4. Connection edges
5. Abstract nodes
6. VAM Syntax

1. Data-flow structure
======================

A model of a microprocessor RTL design is represented by a structure describing
data-flow in a processor. The structure looks like a network of storage and
functional nodes. These nodes are connected by directed edges (node
connections) representing flow of data between nodes. Each node has its input
and output connections.

2. Storage nodes
================

A storage node represents a hardware element able to remember some data for
unspecified period of time. In RTL designs, such elements are either one-bit
flip-flop or latch, register (a vector of flip-flops), register file (an array
of registers), or memory unit (a register file with arbitrary read and write
latencies). In VAM, we support just a subset of these elements. We define I/O
connections for a register and a memory only:

Register, parameters: width >= 1
    - WE (write enable), input, one bit
    - D (data), input, bit vector
    - Q (data), output, bit vector

Memories and register field, parameters: data_bitwidth > 1,
address_bitwidth > 1, 1 < number_of_elements <= 2^address_bitwidth,
    one or more write ports, X is the port identifier
    - WEX (write enable), input, one bit
    - WAX (write address), input, vector of address_bitwidth
    - DX (data), output, vector of data_width
    one or more read ports, X is the port identifier
    - REX (read enable), input, one bit
    - RAX (read address), input, vector of address_bitwidth
    - QX (data), output, vector of data_width

Information about a storage node may change during analysis. In particular
for non-architectural storage nodes, we record the pipeline stage to which
a storage node is assigned.

3. Functional nodes
===================

A functional node represents a function of input to output data. We supports
almost all expresions compatible with an VHDL language:

    * signal assignments: :=
    * integer constants with specified bit-width: (_ value bitwidth)
    * logic operators: ! (not), || (or), && (and)
    * ternary logic operator: ? :
    * bitwise operators: ~ (inverse), | (or), & (and), ^ (xor), << (shl), 
      >> (shr), >>. (sar)
    * relational operators: ==, !=, unsigned <, >, <=, >=, signed <., >., 
      <=., >=.
    * casting operators: bool(vector V) == (V != 0), unsigned<->signed
    * vector operators: V[i] (indexing), . (vector-concatenate),
      ^^ (unsigned vector-resize: V ^^ bitwidth), ^^. (signed vector-resize),
      V[i1..i2] (vector-slice)
    * case-like selections: case(address){case1:EXPR, ..., default:EXPR}
    * integer arithmetic operations: -. (neg), -, +, *,
      unsigned /, unsigned % (mod)

However, in VAM model designated for analysis of its data-flow, we consinder
just a subset of these operations:

    * signal assignments: signal identifier := EXPR
    * integer constants
    * logic operators: ! (not), || (or), && (and)
    * abstracted logic operator: !!(input1, input2, ...)
    * abstracted bitwise operator: ~~(input1, input2, ...)
    * relational operators: ==, !=, unsigned <, >, <=, >=, signed <., >.,
      <=., >=.
    * abstracted relational operator: <>(input1, input2, ...)
    * casting operator: bool(vector V) rewritten as (V != 0)
    * abstracted casting and vector operator: ][(input)
    * case-like selections: case(address){case1:EXPR, ..., default:EXPR}
    * abstracted integer arithmetic operations: -+(input1, input2, ...)
    * all other operators is represented by ~~

Since we introduce an abstracted version of some operators, we use them as
the result of rewritings of expressions which combine several operators:

    Rule 1: logic op. + logic op. ==> !!
    Rule 2: relational op. + relational op. ==> <>
    Rule 3: arithmetic op. + arithmetic op. ==> -+
    Rule 4: bitwise op. + bitwise op. ==> ~~
    Rule 5: bitwise op. + login op. ==> ~~
    Rule 6: casting/vector op. + casting/vector op. ==> ][
    Rule 7: case op. + case op. ==> corresponding non-nested case op.
    Rule 8: arithmetic op. + casting/vector op. ==> -+
    Rule 9: arithmetic op. + relational op. ==> <>
    Rule 10: arithmetic op. + bitwise op. ==> ~~
    Rule 11: logic op. + relational op. ==> !!
    Rule 12: logic/bitwise op. + casting/vector op. ==> ~~
             (in a sense of indexing or casting to bool)
    Rule 13: case op. + nested logic/bitwise/relational/casting/ op. ==>
             no change
    Rule 14: logic/bitwise/relational/casting/ op. + nested case op. ==> ~~
    
For example, the expression:

    x[2] & (y || !(z < 3))              i.e.
    (& ([] x 2) (|| y (! (< z 3))))
    
is rewritten in the following steps:

    0. (& ([] x 2) (|| y (! (< z 3)))
    1. (& ([] x 2) (|| y (!! z 3)       (Rule 11)
    2. (& ([] x 2) (!! y z 3))          (Rule 1)
      interstep 3a: one expression per operand of &-operation:
       (~~ x 2), (~~ y z 3)             (Rule 12, Rule 5)
    3. (~~ x 2 y z 3)                   (Rule 4)
        
Moreover for VAM model designated for data-flow analysis, there are some
restrictions on how functional nodes can connect each other. These restrictions
come from the requirement to encapsulate a given behavior as most as possible
but not too much to be able to provide useful data-flow analysis results. In
particular, if data within functional node flow in/to different directions
within the design, the functional node can be split. Two functional nodes can
be directly connected if it applies to one of the following cases:

    * output of the first node is the input of the second node AND the input
      of a storage node:

            (f1)--(f2)
                \   
                 |s1|

    * inputs of the second node are the output of the first node AND the output
      of a storage node:

            (f1)--(f2)
                  /
              |s1|

    * it is a switch with no common functional node successor:

            (f1)--(f2)--.*--|s1|
                \
                 (f3)--.*--|s2|

    * it is a join of functional nodes with no common functional node
      predecessor:

            |s1|--.*--(f1)--(f2)
                            /
              |s2|--.*--(f3)

4. Connection edges
===================

A connection edge represents a signal carrying some data between nodes. Each
signal may have different bit width, may be named (if it is bound to some
design variable) or unnamed (if it is a part of an expression). A signal
may carry different kind of data such as data, address, or control (or even
combination of them).

A connection edge holds the following (static) information:

    - signal name,
    - bit width, and
    - subset of signal value types (the reason of existance of the connection),
      i.e. data, address, control, unknown


4.1 Connection metadata
~~~~~~~~~~~~~~~~~~~~~~~

Analysis performed on the VAM model consists of several stages. This is why
some information of a connection may change during analysis. These metadata
includes the following:

    - direction of the signal (if it is a part of read or write access) --
      at the moment of writing this specification, it is not clear if the
      information about access direction is important,
    - storages which output directly influence a value of the signal, and
    - the stage to which the signal belongs*.

* In our analysis, we understand the owner stage as the earliest stage of
stages to which influential storages belong.

5. Abstract nodes
=================

Analysis of a microprocessor can not be done without modeling some of its
environment such as I/O devices and memories. In VAM, these are modelled
using abstract nodes. In general, abstract nodes have unspecified input,
output, and undefined behavior. However, it is common that units outside
microprocessor is connected to it via some kind of bus, so the set of
signals and node behavior satisfies the bus specification. In such a case,
an abstract node has assigned the information in which way it communicates
with a microprocessor (e.g., using bus or cache protocol).

6. VAM Syntax
=============

Description of a VAM model is in a single text file with LISP-like syntax. It
consists of general model information, declaration of signals (i.e. connection
edges), declaration of storage nodes, and definition of functional nodes.

General model information has the following form:

    (model
        model_name
        (pipeline-stages list of stage identifiers)
        (sig ...)
        ...
        (reg ...)
        ...
        (regfile ...)
        ...
        (fnodes ...)
        ...
    )

where stage identifier is a common idenfiticator (regexpr [[:alnum:]]+) and
the list of stage identifiers represents the string of pipeline stages. The
rest of the specification (sig, reg, regfile, fnode) is a list of declarations
and definitions of VAM components. Their order does not matter.

Example: (model simple_processor (pipeline-stages fe id ex st mem wb))

Signals
~~~~~~~

A signal is explicitly declared signal used for connecting storage and/or
functional nodes or it is used to express data-flow within a functional node or
a storage node signal. Declaration of a new signal is of the following form

    (sig signal_identifier
        bit_width
        (vt list of value types)
        (dir direction)
        (inputs list of storage identifiers)
        (stage stage_identification)
        (connections list of (storage_id conn))
        (meta ...)
    )

where:

    * signal_identifier is unique identification of the signal used in
      storage and functional nodes (if unnamed, it may be just a positive
      number, otherwise it can not include either white character, parenthesis,
      or dot),
    * bit_width is a positive integer,
    * value type is either 'data', 'address', 'control', or 'unknown',
    * direction of flow of more complex data, in optional (dir ...), has value
      either 'ro' (read only), 'wo' (write only), 'rw' (read-write),
    * optional (inputs ...) represents the set of influential storages,
      i.e. which storages influence a value of the signal,
    * stage_identification, in optional (stage ...), is one of pipeline
      identifiers defined in general model definition,
    * optional connections informing in which storage and connection port
      the signal is connected to (just informal identification).
      The information is ignored at the moment because it is redundant wrt.
      storage definition, see below, and
    * optional (meta ...) with arbitrary information (it is reserved for
      future extensions of VAM).


Example:

    (sig ex_alu 16
        (vt data)
        (dir rw)
        (inputs ex_movi ex_regA ex_regB ex_mem ex_imm ex_movi ex_alu_op)
        (stage ex)
        (meta (loc xyz.codal 156) (loc xyz.codal 287))
    )

which represents a 16-bit signal influenced by several ex_* storages, used
by read and write access, and belonging to the id pipeline stage.

Storages
~~~~~~~~

Declaration of a register storage node is of the following form

    (reg register_identifier
        bit_width
        (d signal_identifier_connected_to_D_port)
        (q list of signal identifiers connected to Q port)
        (we signal_identifier_connected_to_WE_port)
        (stall signal_identifier_connected_to_STALL_port)
        (clr signal_identifier_connected_to_CLEAR_port)
        (rst signal_identifier_connected_to_RESET_port)
        (stage stage_identification)
        (meta ...)
    )

where:
    
    * register_identifier is the identification of the register (it has no
      special meaning at the moment of writing this document). It has to be
      unique identifier of a storage (register or memory),
    * bit_width is a possitive integer (bitwidth = 1 means that the register
      is a flip-flop),
    * we, d, q, stall, clr, and rst defines signals connected to specified
      ports (definitions of stall, clr, and rst are optional),
    * optional (stage ...) defines pipeline stage identification to which
      the register is assigned, and
    * optional (meta ...) contains arbitrary information (it is reserved
      for future extensions of VAM).
    
Declaration of addressable storage (e.g. register file) is of the following
form

    (mem memory_identifier
        bit_width
        address_bitwidth
        number_of_memory_cells
        (ports
            (port port_identifier
                (dir direction)
                (timing delay)
                (en signal_identifier_connected_to_enable_port)
                (addr signal_identifier_connected_to_address_port)
                (data list of identifiers of signals connected to data port)
                (control list of identifiers of control signals)
                (stage stage_identifier)
                (meta ...)
            )
            (port ...)
            ...
        )
        (rst signal_identifier_connected_to_RESET_port)
        (meta ...)
    )

where:
    
    * memory_identifier is unused at the moment. It has to be
      unique identifier of a storage (register or memory),
    * bit_width is a positive number representing the bit width of a memory
      cell,
    * address_bitwidth is a positive number representing the bit width of
      memory address,
    * number_of_memory_cells is a positive number (>1) representing number of
      registers in register file (it should be <= 2^address_bitwidth),
    * (ports ...) sections defines read and write ports (accesses) to the
      register file, the number of ports is not limited,
    * (port ...) contains access port identifier unique for a given register
      file,
    * direction, mandatory for each port, has value either 'ro' (read only),
      'wo' (write only), or 'rw' (read and write),
    * timing specifies the number of clock cycles when accessing the memory
      through the port,
    * en, addr, and data represent enable, address, and data storage node
      port for a given access port (note that there should be just one signal
      connected to en, addr port of any access port and just one signal
      connected to data port of a write access port),
    * control (optional) defines signals (with unspecified semantics) are
      connected to a given port,
    * optional (stage ...) defines pipeline stage identification to which
      a given port is assigned,
    * optional (rst ...) defines a signal connected to reset port, and
    * optional (meta ...) contains arbitrary information (it is reserved
      for future extensions of VAM).

Example:

    (mem regs 16 3 8
        (ports
            (port r0
                (dir ro)
                (timing 0)
                (en v12)
                (addr v14)
                (data v18 v158 v164)
                (stage id))
            (port r1
                (dir ro)
                (timing 0)
                (en v20)
                (addr v22)
                (data v24 v159 v165)
                (stage ex))
            (port w1
                (dir wo)
                (timing 1)
                (en v32)
                (addr v34)
                (data v38)
                (stage wb))
        )
    )

which represents a register file with 8 register of bit width 16 with two
read ports and one write port, where reading takes no delay while writing is
one-cycle delayed.

Functional nodes
~~~~~~~~~~~~~~~~

A functional node contains the list of assignments. Each assignment binds
a functional node output to an expression. Expressions is either:

    1. constant,
    2. signal identifier, or
    3. an operator over expressions.

Definition of a functional node has the following form:

    (fnode fnode_identifier
        (input list of signal idenfitications)
        (output list of signal idenfitications)
        (stage stage_identification)
        (assign
            (:= output_signal_identifier expression)
            (:= output_signal_identifier expression)
            ...
        )
        (meta ...)
    )

where:

    * fnode_identifier is used to identify functional node input/output
      signals,
    * optional (stage ...) defines pipeline stage identification to which
      the functional node is assigned,
    * (assign ...) part defines assignments of functional node outputs to
      expressions (each output signal has just one assignment), and
    * optional (meta ...) contains arbitrary information (it is reserved
      for future extensions of VAM).

Example:

    (fnode f128
        (input ex_regA_q ex_regB_q ex_op_q)
        (output ex_alu_d)
        (stage ex)
        (assign
            (:= ex_alu_d_1 (?
                    (== ([..] ex_op_q 0 3) 5)
                    (+ ex_regA_q ex_regB_q) 0)
            )
            (:= ex_alu_d_2 (?
                    (== ([..] ex_op_q 0 3) 4)
                    (-. ex_regA_q ex_regB_q) 0)
            )
            (:= ex_alu_d_3 (?
                    (== ([..] ex_op_q 0 3) 3)
                    (- ex_regA_q) 0)
            )
            (:= ex_alu_d (| ex_alu_d_1 ex_alu_d_2 ex_alu_d_3))
        )
    )

Operators:

    * signal assignments:
        (:= target_signal_id expr)
    * integer constants with specified bit-width:
        (_ value bitwidth)
    * logic operators:
        not: (! expr)
        or: (|| list of expressions)
        and: (&& list of expressions)
    * ternary logic operator:
        (? cond_expr expr_true expr_false)
    * bitwise operators: 
        inverse: (~ expr)
        or: (| expr1 expr2)
        and: (& expr1 expr2)
        xor: (^ expr1 expr2)
        shift left a << b: (<< a_expr b_expr)
        shift right a >> b: (>> a_expr b_expr)
        shift-arithmetic right a >> b: (>>. a_expr b_expr)
    * relational operators:
        equality: (== expr1 expr2)
        inequality: (!= expr1 expr2)void
        unsigned less-than: (< expr1 expr2)
        unsigned greater-than: (> expr1 expr2)
        unsigned less-or-equal: (<= expr1 expr2)
        unsigned greater-or-equal: (>= expr1 expr2)
        signed less-than: (<. expr1 expr2)
        signed greater-than: (>. expr1 expr2)
        signed less-or-equal: (<=. expr1 expr2)
        signed greater-or-equal: (>=. expr1 expr2)
    * casting operators:
        vector-to-bool: (!= expr 0)
        unsigned-to-signed: (-. expr) // TODO: useful?
        signed-to-unsigned: (.- expr) // TODO: useful?
    * vector operators:
        indexing V[i]: ([] V_expr i_expr)
        bit extraction: ([.] V_expr index_constant)
        concatenation of vectors V1+V2: (. V1_expr V2_expr)
        unsigned vector extension: (^^ vector_expr bitwidth_constant)
        signed vector extension: (^^. vector_expr bitwidth_constant)
        vector slicing V[i1..i2]: ([..] V_expr i1_constant i2_constant)
    * case-like selections:
        case(address){case1:EXPR1, ..., default:EXPR1}:
            (switch address_expr
                (case1_value_expr value1_expr)
                (case2_value_expr value2_expr)
                ...
                (default_value_expr)
            )
        more general conditions:
            (cond
                (condition1_expr value1_expr)
                (condition2_expr value2_expr)
                ...
                (default_value_expr)
            )
    * integer arithmetic operations:
        negation: (-- expr)
        plus, minus, multiply: (+ L_expr R_expr), resp. (- ...), (* ...)
        unsigned divide: (/ dividend_expr divisor_expr)
        unsigned modulo: (% dividend_expr divisor_expr)
    * abstract operations:
        abstract logic: !!
        abstract bitwise: ~~
        abstract relational: <>
        abstract vector: ][
        abstract arithmetic: -+