operation fusion/morphing

[tygaribay-gh]

[jeffnye-gh]

Start of a discussion on instruction/op fusion.

Issue raised originally by zxc12523 and discussion suggested by Knute in #113.

This is the start of that discussion, as suggested the outcome would be a description of the API for instructions transformed in decode, and a discussion of implementation choices, and a sample implementation with unit test.

The original interest was in fusion but I think of this as a more general need for instruction transforms, where fusion is one transform and fracture is another. The former has more interest at this point of the RV ISA, but the allowance of custom instructions and as yet unknown future extensions suggests fracturing may also be of interest at some point.

I would like an API that could accommodate both transformations.

(if someone can remove the initial post, tygaribay-gh, I was logged into a test account, and submitted before I realized it.)

[jeffnye-gh]

Attached is a rough draft of a design document. Posted for guidance on general direction but I welcome any feedback.

In the current state of the API document, I have scoped the definition of the problem and created a set of basic methods that let me explore mechanics of legalization and transformation. I am creating a fusion unit and a test bench for it.

I am currently leaning toward user registered callbacks because they make the API inherently independent of file format specifications of fusion/fracture operations. For the general case I expect there to be many ways to specify the transform process.

In the first example I am implementing I am using callbacks with the fusion specification relying on Mavis/Json. I also expect there to be an STF utility function for transformation of trace records. The goal is to propose no modification to either standard.

fusion_api_design_doc.pdf

[jeffnye-gh]

Abandoning the PDF for now. Below is a long-ish summary. Suggestions and opinions invited.

As given: Fusion compares an incoming sequence of instructions to a set of known sequences, constraints and transforms. Incoming sequences that match known sequences and meet the constraints have the fusion transform performed. The incoming sequence is replaced with the fusion result and passed downstream.

A simplified sequence from dhrystone, chosen at random not because it warrants fusion.

0000000080000000 <_start>:
    80000000: 4081    li  ra,0    # ra = x1  UID = 0x13
    80000002: 4101    li  sp,0    # sp = x2  ...
    80000004: 4181    li  gp,0    # gp = x3  ...
    80000006: 4201    li  tp,0    # tp = x4  ...
    80000008: 4281    li  t0,0    # t0 = x5  ...
    8000000a: 4301    li  t1,0    # t1 = x6  ...
    8000000c: 4381    li  t2,0    # t2 = x7  ...
    8000000e: 4401    li  s0,0    # s0 = x8  UID = 0x13
    ...snip...

The instruction li rd,imm has the mavis unique identifier 0x13.

Assume the pre-registered sequences are expressed as transforms (Tx), constraints (Cx) and sequence tuples [...];

  { T1,  Cn, [0x13, 0x13] },
  { T2,  Cn, [0x13, 0x13, 0x13] },
  { T3,  Cn, [0x13, 0x13, 0x13, 0x13] }
  ...snip...

The arrays of UIDS are replaced with a hash in the model.

The abstract transforms take the form:

T1 = li rd1:rd2,0       # UID 0x13+magic1
T2 = li rd1:rd3,0       # UID 0x13+magic2
T3 = li rd1:rd4,0       # UID 0x13+magic3

The transform results in a re-encoding to a custom instruction understood by the hardware.

The abstract contraints take the form:

Cn  =  WR <= 4  & RD <= 8  & RS == 0

WR = number of write ports required by the new instruction
RD = number of read ports required by the new instruction
RS = the immediate operand

The transform and constraints are implemented in callbacks.

The transform process uses greedy matching with a minimum tuple size of N and a maximum tuple size of M. N and M are parameters.

If the incoming sequence is re-written as A B C D..., the ordered combinations of tuples are:

ABCD BCDE CDEF DEFG EFGH      # [0x13 0x13 0x13 0x13] => HASH
ABC BCD CDE DEF EFH FGH       # [0x13 0x13 0x13]      => HASH
AB BC CD DE EF FG GH          # [0x13 0x13]           => HASH
...etc...

Beginning with the longest sequence the HASHes are compared to the HASH of the preregistered tuples and the contraints are tested. The first combination that meets the contraints is also the longest valid sequence.

The transform of the matching preregistered sequence is applied to the operands of the combination tuple.

This is another example of supporting generality in the model. The hardware would perform comparison in parallel and priority select the longest match.

The matching incoming sequences are replaced with the transform result in the output and the process continues until the incoming sequence is exhausted. Of course in cases where no valid transform is found the incoming sequence is copied to the output.

In this simple case the result is two complex instructions, the syntax is here for reference. I have not done anything for a working disassembler.

0000000080000000 <_start>:
    80000000: ----    li  x1:x4,0
    800000--: ----    li  x5:x8,0
    ...snip...

The preregistered sequences are represented in json and use the mavis UID as the reference key. The values of constraint_set and transform are the names of the callbacks.

{
  "fusable_sequences" : [
    { "hash" : "0x12",
      "stencil_sequence" : [ "0x13", "0x13" ],
      "constraint_set"   : "constraint_Cn",
      "transform"        : "transform_T1"
    },
    { "hash" : "0x345",
      "stencil_sequence" : [ "0x13", "0x13", "0x13" ],
      "constraint_set"   : "constraint_Cn",
      "transform"        : "transform_T2"
    },
    { "hash" : "0x6789",
      "stencil_sequence" : [ "0x13", "0x13", "0x13", "0x13" ],
      "constraint_set"   : "constraint_Cn",
      "transform"        : transform_"T3"
    }
  ]
}

[klingaard]

Dave Murrell (@dbmurrell) since you're an expert on fusion as well, do you want to provide any ideas/feedback to this discussion?

[arupc]

Thank you Jeff for putting this together.
@rajatbhatia1 Can you please review the proposal and share your comments?

[jeffnye-gh]

Below is a sample showing more of the direction. I have an LALR parser, there are no shift/reduce problems. The domain context has eliminated the need for some common syntax. Not shown but the parser grammar also a supports flattened form and a form which improves reuse. I have example transform syntax below which I did not have before, work in progress.

This case is shorter than the previous, it uses operand positions as a constraint, e.g. all g1 are the same. Making the assumption the input instruction was properly encoded saves a lot of value checking statements. I've added one contrived constraint, g1 != g2

Next is to try an implementation and prove the matching and constraints checking.

 1. fusion fs1 {
 2.
 3.   isa   rv64g
 4.   uarch oly1
 5.   input_seq in_seq
 6.
 7.   sequence seq1(in_seq,rv64g) {
 8.     c.lui    g1, c1
 9.     c.addi   g1, g1, c2
10.     _req_
11.     c.xor    g2, g2, g1
12.     c.slli   g2, g2, c3
13.     _opt_
14.     c.srli   g2,     c3
15.   }
16.
17.   constraints cons1(seq1,in_seq,rv64g,oly1) {
18.     gpr g1,g2
19.     g1 != g2
20.   }
21.
22.   transform t1(seq1,cons1) {
23.     encoding word1(seq1,opc) {
24.       u10 opc    //57:48   unsigned 10b
25.       u6  c3     //47:42   unsigned 6b
26.       s12 c2     //41:30   signed 12b
27.       s20 c1     //29:10   signed 20b
28.       gpr g1     //9:5     gpr 5b
29.       gpr g2     //4:0     gpr 5b
30.       encode_order(opc,c3,c2,c1,g1,g2)
31.     }
32.     emit(word1(seq1,opc=0x234))
33.   }
34. }

[rajatbhatia1]

I have reviewed the proposal and it looks good. I have just one comment, and it is more in line of how this will be integrated into Olympia. I propose that we should define a instruction fusion interface, and the proposal above will be one implementation of the interface. This will allow the users to write their own fusion model, if the proposal is not sufficient for their microarchitecture needs.

[jeffnye-gh]

fusion_api_draft.pdf

Attached is a PDF of the doxygen latex for the current snapshot of the C++ API. This is from a testbench. Work remains but the callback idiom is presented. There is also a riscv-perf-model Decoder unit test in progress, it is incomplete.

I've made some assumptions about the capabilities of the support code:

• I assume there is a class which I can query the static information about the implementation of the machine, write/read ports, computation sites present. pg. 24 covers static and dynamic queries of the machine.

• I assume there are methods in Mavis where I can access encoding fields by name, and extract values from the encoding. See constraints callback description on pg. 26 and 7.4.2.1

• FusionBench is part of this documentation but not an intended part of the API. The references to the sequence zoo are not part of the API, they are test cases

• The todo list has some opens, there are more unlisted.

The top level methods in a use case are:

searchSequence
matchConstraints
executeTransform

also registerSequence is a startup/initialization process, which builds the fusion sequences at run time. I'm focusing on getting something functional in the Decoder testbench. I'll revisit something more in-line with the tree construction methods used in the model

There is work remaining. Feedback is always welcome.

[jeffnye-gh]

This is a working function object for checking constraints for a fusion group. The API handles field value queries of the input using mavis and access to machine implementation details.

These implementation details, such as read and write port limits, will affect performance correlation with fusion. In the current implementation I use parameters added to the Decode unit.

If there is time in the next call I'd like to discuss if there is a more general way to handle these implementation details.

pdf had Sequence this is now FusionGroup.

// --------------------------------------------------------------------
// zoo.F1 specific checks
//
//   Operand requirements
//     - rgrp[0].RD  == rgrp[1].RD == rgrp[2].RS1
//     - rgrp[2].RD  == rgrp[3].RD == rgrp[4].RD
//     - rgrp[3].IMM == rgrp[4].IMM
// --------------------------------------------------------------------
bool F1_constraints(FusionGroup &g,const inst_vec_t &input)
{
  //number of wr/rd ports required by group tested against machine limits
  if(g.getIntWrPorts(input) > g.maxIntWrPorts()) return false;
  if(g.getIntRdPorts(input) > g.maxIntRdPorts()) return false;

  using enum FusionGroup::FieldName;

  //Operand field encodings comparison against constraints
  //The indexes are positions in the group, 0 = 1st instruction
  if(g.noteq(input,0,1,RD)       ||
     g.noteq(input,0,2,RD,RS1)   ||
     g.noteq(input,2,3,RD)       || //compare the RD fields of instrs 2 and 3
     g.noteq(input,2,4,RD)       ||
     g.noteq(input,3,4,IMM))
  {
    return false;
  }

  return true;
}

[klingaard]

Still digesting your fusion proposal... but I did find some time to build a small "instruction dumper" that illustrates the use of Mavis to find pairings.

Checkout the branch knutel/mavis_dump_inst from the master olympia repo. Build the tool, dump_inst:

git co knutel/mavis_dump_inst
cd <build dir>
cmake ..
cd tools/dump_inst
make

Try these examples:

# Fusable:
# b4078793 addi        x15,x15,-1216 # 0x00023b40
# 00006398 c.ld        x14,0(x15)

./dump_inst -p 0xb4078793,0x00006398

# Not Fusable:
# f00507d3 fmv.w.x     f15,x10
# 00006398 c.ld        x14,0(x15)

./dump_inst -p 0xf00507d3,0x00006398

[klingaard]

You can also use this tool to see how to go from mnemonic -> mavis id (although I don't print that out right now):

./dump_inst -m addi

[jeffnye-gh]

I appreciate this, thank you.

I would hold off further review until the draft PR. I am re-structuring the code to conform to existing style/idioms in riscv-perf-model. What I previously showed helped me explain the thought process without regard to conventions, I want to align the interfaces and style to what's in the codebase.

I appreciate the guidance on mavis. The constraints example above uses mavis to extract fields and convert between representations. At the moment I'm looking at radix-trie alternatives to the Mavis d-trie, since the search is primarily uint32_t/uint64_t.

I will post here when I've submitted the draft.

[jeffnye-gh]

Draft PR posted.

fusion draft PR commit #135

[jeffnye-gh]

thanks for your review knute, I've pushed the requested changes. I have a set of changes that begins to create the AST for the language. I'll hold these for now.

I'd like to have a discussion on the dsl (calling it FSL for now). There are a number of ways to go, It would be interesting to solicit ideas before the syntax/grammar solidifies.

[jeffnye-gh]

Longer than I hoped because of the explanation.

From the last call, speaking to why a new syntax makes sense. Here's one view of what the dsl (FSL) could look like in Python. This is pseudo code, I have not implemented any of the Python wrappers.

Below is an FSL example, a 5-instruction group with constraints. For simplicity, it omits the 'req' and 'opt' placeholders and transform syntax.

In use you could imagine the model starts up a python interpreter reads these files and populates the Fusion API structures at run time. This is similar to how the FSL interpreter works.

FSL interpreter is smaller than a Python interpreter and will have a smaller run time footprint.

1. fusion fs1 {
2.
3.   isa   rv64gc
4.   uarch oly1
5.   inseq in\_seq
6.
7.   sequence seq1(in\_seq,rv64gc) {
8.     c.lui    g1, c1
9.     c.addi   g1, g1, c2
10.     _req_
11.     c.xor    g2, g2, g1
12.     c.slli   g2, g2, c3
13.     _opt_
14.     c.srli   g2,     c3
15.   }
16.
17.   constraints cons1(seq1,in\_seq,rv64gc,oly1) {
18.     gpr g1,g2
19.     s20 c1
20.     s12 c2
21.     u6  c3
22.
23.     g1 != g2
24.   }
25. }

Below is what I think it looks like to reproduce the FSL features in python. Again this is pseudo code.

import  olympia as Olympia
import  mavis   as Mavis
import  fusion  as Fusion

yaml_file = './arches/big_core.yaml'

oly    = Olympia()
try:
   uarch  = oly.getImplementation(yaml_file) 
except:
   ...

try:
   inseq  = uarch.getUnit('decoder').getContainer('fetch_queue_')
except:
   ...

rv64gc = [
'./mavis/json/isa_rv64g.json',
'./mavis/json/isa_rv64c.json'
]


mavis  = Mavis()
try:
   isa = mavis.getFacade(rv64gc)   # get a mavis instance w/ the ISA
except:

group = [
  ('c.lui',  ['g1', 'c1']),
  ('c.addi', ['g1', 'g1', 'c2']),
  ('_req_',  []),
  ('c.xor',  ['g2', 'g2', 'g1']),
  ('c.slli', ['g2', 'g2', 'c3']),
  ('_opt_',  []),
  ('c.srli', ['g2', 'c3'])
]

fusion = Fusion()

try:
  seq1 = fusion.formGroup(group,isa,inseq)
except:
  ...

  cons1 = fusion.getConstraintsInstance()
  cons1.declareTypes('gpr',('g1','g2'))
  cons1.declareTypes('s20','c1')
  cons1.declareTypes('s12','c2')
  cons1.declareTypes('u6','c3')
  cons1.declareExpression(notequal,'g1','g2')

try:
  seq1 = const1.applySequence(seq1)
except:
...

Once all the python files have been loaded the model proceeds normally.

The above presumes support in Python/C++ via something like Boost::Python. This is overhead not present in a native FSL implementation.

What is implemented assumes speed is important so rather than native Python there is an assumption of support in C++ instead, e.g. the FSL::sequence and FSL::constraints. Wrapping these classes is overhead in the API.

FSL uses the concept of an instruction with abstract operands. This is native to the FSL parser to support it through python requires writing the support methods in C++ and the wrappers.

In python you would build your fusion group from a list of strings, a reference to the Mavis Facade, and the input container.

Creating the constraints is problematic. Unless you reuse the expressions found in the FSL parser, which diminishes the value of python somewhat, you would need to create a way to describe constraint expressions or bring more of the C++ API into a native python implementation so you could use normal python statements for the constraint expression. This would be more Python overhead than what I show above and below.

These are the constraints in FSL:

17.   constraints cons1(seq1,in_seq,isa) {
18.     gpr g1,g2
19.     s20 c1
20.     s12 c2
21.     u6  c3
22.
23.     g1 != g2
24.   }

A possible python version:

fusion = Fusion()

try:
  seq1 = fusion.formGroup(group,isa,inseq)
except:
  ...

  cons1 = fusion.getConstraintsInstance()
  cons1.declareTypes('gpr',('g1','g2'))
  cons1.declareTypes('s20','c1')
  cons1.declareTypes('s12','c2')
  cons1.declareTypes('u6','c3')
  cons1.declareExpression(notequal,'g1','g2')

try:
  seq1 = const1.applySequence(seq1)
except:
...

These constraints are simple, it is easy to see how cumbersome this could become with more complicated constraints. There is overhead in the API to support this Python based expression of constraints.

There are more topics on the syntax justification, such as re-use of fusion groups and constraints that would need additional support through a combination of Python syntax and Fusion API wrappers.

[jeffnye-gh]

@klingaard I have pushed all the review changes I have on the fusion PR.

thank you everyone.

[jeffnye-gh]

From the last call I captured these ARs for Fusion.

• Write up a document concerning the language. I just posted #160

• Post a decoder that uses fusion. Work in progress.

[jeffnye-gh]

PR #163

This is the oly decoder with fusion support using UIDs.

[jeffnye-gh]

I plan to add a report def file for reporting IPC with and without fusion. I am looking for some help on the report mechanism.

The dhry_report.yaml is similar to what I'd like. I am unable to get it to find the top node.
Could not find any nodes matching the pattern "top" from nodes [top,]. In file reports/dhry_report.yaml:6 col:4

I modified a copy of reports/core_report.def (as ./dhry_report.def) to contain this:

content:
  report:
    pattern:   top
    def_file:  reports/dhry_report.yaml
    dest_file: my_dest.txt
    format:    text

From release I executed

./olympia -i1M ../traces/dhry_riscv.zstf --auto-summary off    \
   --report ./dhry_report.def \
   --report-search reports

Can anyone tell me what I am doing wrong?

[klingaard]

The def file has the pattern to "start" from as top. In dhry_report.yaml it's repeated:

content:
  top:

So the report class is told to look for top.top.

I think you can remove the pattern from the def file OR change it to "". Not sure if that'll work, but could try

[jeffnye-gh]

I removed pattern: top, works now, thank you.

[zxc12523]

Repost the question as @arupc suggested.

riscv-perf-model/fusion/fusion/HCache.hpp

Line 78 in a0f965f

hcache.insert(make_pair(grpSize,cacheLine));

riscv-perf-model/fusion/fusion/HCache.hpp

Line 161 in a0f965f

std::map<size_t,HashPairListType> hcache;

Won't different fgPairs have the same grpSize? If they are, will this line of code be wrong?

[jeffnye-gh]

Thanks for your question. I believe the code is correct. buildHashCacheEntry() inserts the length permutations of inputUids and their jenkins hash into hcache_. The conditions where fgPairs have the same size is what gives the hcache it's benefit.

I have a local branch with an enhancement which adds an early exit buildHashCacheEntry() plus some other clean up.

[jeffnye-gh]

Our crunch is still on going, but I found some time to finish a draft of the parser syntax. If you like these sorts of things this is the BNF, there is broader, ideally more symmetrical, support for expressions.

Next steps: I am now creating a more extensive document, including use cases from public benchmarks.
After that I presume a more extensive review from those with interest.

<top> ::= <source_line> | <top> <source_line>

<source_line> ::= <transform_definition> | <prolog_definition> | <declaration>

<transform_definition> ::= TRANSFORM <id> '{' '}' | TRANSFORM <id> '{' <transform_statements> '}'

<transform_statements> ::= <transform_statement> | <transform_statements> <transform_statement>

<transform_statement> ::= PROLOG <id> | <isa_decl> | <uarch_decl> | <ioput_decl> | <variable_decl> | <selection_statement> | <constraints_definition> | <conversion_definition> | <setof_definition>

<setof_definition> ::= SETOF <id> '=' <chained_id_list> '.' <chained_method_list>

<chained_method_list> ::= <chained_method_list> '.' <known_method_decl> | <known_method_decl>

<known_method_decl> ::= <known_method> '(' <opt_arg> ')'

<opt_arg> ::= /* empty */ | <id> | <constant> | '{' '}' | '*' | '{' <concatenate_list> '}'

<prolog_definition> ::= PROLOG <id> '{' '}' | PROLOG <id> '{' <prolog_statements> '}'

<prolog_statements> ::= <prolog_statement> | <prolog_statements> <prolog_statement>

<prolog_statement> ::= ISA <id> | UARCH <id> | IOPUT <id>

<isa_decl> ::= ISA <id>

<uarch_decl> ::= UARCH <id>

<ioput_decl> ::= IOPUT <id>

<variable_definition> ::= <type_specifier> <id> '=' <assignment_expression> | <type_specifier> <id> '=' '{' <concatenate_list> '}'

<variable_decl> ::= <type_specifier> <arg_expr_list> | <variable_definition>

<constraints_definition> ::= CONSTRAINTS <opt_id> '{' <constraints_statements> '}' | CONSTRAINTS <id> '(' <arg_expr_list> ')' '{' <constraints_statements> '}'

<opt_id> ::= /* empty */ | <id>

<constraints_statements> ::= <constraints_statement> | <constraints_statements> <constraints_statement>

<constraints_statement> ::= <pass_fail_statement> | <chained_id_list> <comparison_operator> <chained_id_list> | <chained_id_list> <comparison_operator> <constant> | <chained_id_list> <comparison_operator> <chained_id_list> LEFT_OP <constant> | <chained_id_list> '.' <known_method_decl> <comparison_operator> <chained_id_list> '.' <known_method_decl> | <chained_id_list> '.' <known_method_decl> <comparison_operator> <constant> | <selection_statement>

<comparison_operator> ::= LE_OP | GE_OP | EQ_OP | NE_OP

<conversion_definition> ::= CONVERSION <opt_id> '{' <conversion_statements> '}' | CONVERSION <id> '(' <arg_expr_list> ')' '{' <conversion_statements> '}'

<conversion_statements> ::= <conversion_statement> | <conversion_statements> <conversion_statement>

<conversion_statement> ::= <pass_fail_statement> | <variable_decl> | <encoding_decl> | <encoding_definition> | <instr_decl> | <instr_definition> | <chained_id_list> '.' <known_method_decl> | <chained_id_list> '.' REPLACE '(' <comma_sep_list> ')'

<concatenate_list> ::= <concatenate_elem> | <concatenate_list> ',' <concatenate_elem>

<concatenate_elem> ::= <id> | <id> <range_list> <opt_dot_id> | OPC | <constant> | <known_method> '=' <constant>

<opt_dot_id> ::= /* empty */ | '.' <id>

<comma_sep_list> ::= <id> | <comma_sep_list> ',' <id>

<range_list> ::= '[' <constant> ']' | '[' <constant> ':' <constant> ']' | <range_list> '[' <constant> ']' | <range_list> '[' <constant> ':' <constant> ']'

<chained_id_list> ::= <id> | <chained_id_list> '.' <id>

<known_method> ::= MNEMONIC | ENCODE_ORDER | WRITEPORTS | READPORTS | REQUIREDBITS | ENCODING | OPC | SRC | DST | RSX | IMM | TYPE | HASATTR | MORPH

<instr_decl> ::= INSTR <id>

<instr_definition> ::= INSTR <id> '(' <arg_assignment_list> ')' | INSTR <id> '(' '{' <concatenate_list> '}' ')' | INSTR <id> '(' '{' <encode_list> '}' ')' | INSTR <id> '(' <chained_id_list> '.' <known_method> '(' <id> ')' ')' | INSTR <id> '(' <known_method> '(' <id> ')' ')'

<encode_list> ::= <encode_elem> | <encode_list> ',' <encode_elem>

<encode_elem> ::= <id> '[' <constant> ']' '.' ENCODING

<encoding_decl> ::= ENCODING <id>

<encoding_definition> ::= ENCODING <id> '(' <arg_assignment_list> ')' | ENCODING <id> '(' '{' <concatenate_list> '}' ')'

<arg_assignment_list> ::= <arg_assignment> | <arg_assignment_list> ',' <arg_assignment>

<arg_assignment> ::= <known_method> '=' <constant> | <known_method> '=' '{' <arg_expr_list> '}' | <id> '=' '{' <arg_expr_list> '}'

<pass_fail_statement> ::= PASS | FAIL

<primary_expression> ::= <id> | <constant> | STRING_LITERAL | '(' <expression> ')'

<postfix_expression> ::= <primary_expression> | <postfix_expression> '[' <expression> ']' | <postfix_expression> '(' <opt_arg_expr_list> ')' | <postfix_expression> '.' <id> | <postfix_expression> INC_OP | <postfix_expression> DEC_OP | <postfix_expression> '.' ENCODING '(' ')'

<opt_arg_expr_list> ::= /* empty */ | <arg_expr_list>

<arg_expr_list> ::= <assignment_expression> | <arg_expr_list> ',' <assignment_expression>

<unary_expression> ::= <postfix_expression> | INC_OP <unary_expression> | DEC_OP <unary_expression> | <unary_operator> <cast_expression>

<unary_operator> ::= '&' | '*' | '+' | '-' | '~' | '!'

<cast_expression> ::= <unary_expression> | '(' <type_name> ')' <cast_expression>

<multiplicative_expression> ::= <cast_expression> | <multiplicative_expression> '*' <cast_expression> | <multiplicative_expression> '/' <cast_expression> | <multiplicative_expression> '%' <cast_expression>

<additive_expression> ::= <multiplicative_expression> | <additive_expression> '+' <multiplicative_expression> | <additive_expression> '-' <multiplicative_expression>

<shift_expression> ::= <additive_expression> | <shift_expression> LEFT_OP <additive_expression> | <shift_expression> RIGHT_OP <additive_expression>

<relational_expression> ::= <shift_expression> | <relational_expression> '<' <shift_expression> | <relational_expression> '>' <shift_expression> | <relational_expression> LE_OP <shift_expression> | <relational_expression> GE_OP <shift_expression>

<equality_expression> ::= <relational_expression> | <equality_expression> EQ_OP <relational_expression> | <equality_expression> NE_OP <relational_expression>

<and_expression> ::= <equality_expression> | <and_expression> '&' <equality_expression>

<exclusive_or_expression> ::= <and_expression> | <exclusive_or_expression> '^' <and_expression>

<inclusive_or_expression> ::= <exclusive_or_expression> | <inclusive_or_expression> '|' <exclusive_or_expression>

<logical_and_expression> ::= <inclusive_or_expression> | <logical_and_expression> AND_OP <inclusive_or_expression>

<logical_or_expression> ::= <logical_and_expression> | <logical_or_expression> OR_OP <logical_and_expression>

<conditional_expression> ::= <logical_or_expression> | <logical_or_expression> '?' <expression> ':' <conditional_expression>

<assignment_expression> ::= <conditional_expression> | <unary_expression> <assignment_operator> <assignment_expression>

<expression> ::= <assignment_expression> | <expression> ',' <assignment_expression>

<assignment_operator> ::= '='

<declaration> ::= <declaration_specifiers> ';' | <declaration_specifiers> <init_declarator_list> ';'

<declaration_specifiers> ::= <storage_class_specifier> | <storage_class_specifier> <declaration_specifiers> | <type_specifier> | <type_specifier> <declaration_specifiers>

<init_declarator_list> ::= <init_declarator> | <init_declarator_list> ',' <init_declarator>

<init_declarator> ::= <declarator> | <declarator> '=' <initializer>

<storage_class_specifier> ::= EXTERN | AUTO

<type_specifier> ::= GPR | CSR | UN_CONST | S_CONST | STRING

<declarator> ::= <direct_declarator>

<direct_declarator> ::= <id> | '(' <declarator> ')' | <direct_declarator> '[' '*' ']' | <direct_declarator> '[' <constant> ']' | <direct_declarator> '[' <constant> ':' <constant> ']' | <direct_declarator> '[' ']' | <direct_declarator> '(' <parameter_list> ')' | <direct_declarator> '(' <identifier_list> ')' | <direct_declarator> '(' ')'

<parameter_list> ::= <parameter_declaration> | <parameter_list> ',' <parameter_declaration>

<parameter_declaration> ::= <declaration_specifiers> <declarator> | <declaration_specifiers>

<identifier_list> ::= <id> | <identifier_list> ',' <id>

<type_name> ::= <specifier_qualifier_list>

<specifier_qualifier_list> ::= <type_specifier> | <type_specifier> <specifier_qualifier_list>

<initializer> ::= <assignment_expression> | '{' <initializer_list> '}' | '{' <initializer_list> ',' '}'

<initializer_list> ::= <initializer> | <initializer_list> ',' <initializer>

<statement> ::= <pass_fail_statement> | <compound_statement> | <expression_statement> | <selection_statement> | <iteration_statement>

<compound_statement> ::= '{' '}' | '{' <block_item_list> '}'

<block_item_list> ::= <block_item> | <block_item_list> <block_item>

<block_item> ::= <declaration> | <statement>

<expression_statement> ::= ';' | <expression> ';'

<selection_statement> ::= IF '(' <expression> ')' <statement> %prec NO_ELSE | IF '(' <expression> ')' <statement> ELSE <statement>

<iteration_statement> ::= FOR '(' <expression_statement> <expression_statement> ')' <statement> | FOR '(' <expression_statement> <expression_statement> <expression> ')' <statement> | FOR '(' <declaration> <expression_statement> ')' <statement> | FOR '(' <declaration> <expression_statement> <expression> ')' <statement>

<id> ::= ID

<constant> ::= CONSTANT | HEX_CONST | VLOG_CONST | QSTRING