Table of Contents

Literal HTML code for export

Verilog Synthesis [2018-08-31 Fri 21:26]

Ok just getting started with this. Optimization should not be the goal for this project. It would be nice if there was isomorphism from schematic to verilog.

Gate-level synthesis [2018-09-19 Wed 15:12]

nb. Place and route will be another stage.

Design

  • Each device will be a node in a graph with in ports, out ports, in/out ports. Does the source for the cell library have to be duplicated, or is it accessible from here? Don't duplicate it. If it's not accessible, make it so.

Plan

6.884 L05 slides: steps from Page 5

  • infer logic and state elements
  • perform technology-independent optimizations (SKIP)
  • map elements to the target technology
  • perform technology-dependent optimizations (SKIP)
  • Throw errors on unsynthesizable AST nodes

    Identify unsynthesizable AST nodes and error nicely. (easy once they are known). Thankfully, this is a large subset of the AST, so looking backwards to the parser, it's not necessary to even parse those, so that code can be removed, though maybe the parser will be used elsewhere, so don't remove it yet.

    • docs for what is synthesizable
      • springer
      • http://asic-soc.blogspot.com
      • http://corevlsi.blogspot.com
      • Non-Syntesizable
        • TODO fork and join
        • TODO force and release
        • TODO delay
        • TODO wait
        • TODO initial
        • TODO time
        • TODO real
        • TODO system tasks
        • TODO event
        • TODO tri0
        • TODO tri1
        • TODO pullup
        • TODO pulldown
        • TODO pmos
        • TODO nmos
        • TODO cmos
        • TODO rpmos
        • TODO rnmos
        • TODO rcmos
        • TODO tranif0
        • TODO tranif1
        • TODO rtran
        • TODO rtranif0
        • TODO rtainif1
        • TODO =
        • TODO !==
        • TODO Event trigger (->)
  • Support explicit structural form
    module and8( input data[7:0], output out);   
  assign out = ((data[0] & data[1]) & (data[2] & data[3])) & 
               ((data[4] & data[5]) & (data[6] & data[7]));
endmodule
  • TODO Support implitict structural form
  • TODO Support synthesizable behavioral

Verification

Formal Proof of Petri Net Refinement using Coq Towards Verifying Petri Nets: A Model Checking Approach Model checking of time Petri nets

Questions

When must a gate be lenient? If it does then Would a javascript based SAT solver be useful for optimizing? How to pick Adders, Multipliers?

Verilog Formatter [2018-07-29 Sun 10:22]

the code for this can be found @ https://github.com/drhodes/jade/blob/exp/verilog_pprint.js

The purpose of this program is not to perfectly format verilog code, but rather to kick the tires on the AST generated by the parser. It found a flaw in how the CHOICE parser rule built indistinguiable nodes, which was addressed with id tags.

First Pass [2018-07-29 Sun 11:37]

So, I thought it would be a good idea to build a code formatter to ensure the parser worked correctly. A formatter should be easy enough to test. Take some verilog source, edit it by hand to meet a standard, run the formatter on it then diff the formatted output with the original. Great!

Except, building a decent formatter is difficult. Shield your eyes, for these are the trials of those who have come before.

dartfmt

gofmt

The first problem to creep in was a mismatch between walking the AST, and the shape of the grammar. The vertical placement of the "begin" keyword isn't determined by grammar, that choice is left to the discretion of the designer.

An aside: What could grammars do to make formatting code easier? 

module blinker( input clk, output reg [31:0] B);   
   reg [31:0] idx = 0;
   always @(posedge clk) begin  
      idx <= idx + 1;
      if (idx % 1000 == 0) begin
         B <= B + 1;
      end
   end   
endmodule

The first pass transforms the above into a simpler intermediate format tree that preserved nested indentation that would be onerous to deal with otherwise. The following is a flattened view of the tree contents. 

`timescale·1ns·/·1ps↓∇↓module·blinker·
ε(input·ε·ε·ε·clk,·output·reg·ε·[31:0]·Bε);
<INDENTED:reg·ε·[31:0]·idx·=·0;
↓always·@(posedge·clk)·begin·idx·<=·ε·idx·+·1;
·if·(idx·%·1000·==·0)
<INDENTED:begin·B·<=·ε·B·+·1;·end>
·end>
endmodule
Symbol meaning
↓ one unit of vertical space
∇ one explicit new line (forced vertical whitespace)
· one unit of horizontal space
ε empty,

Heuristics

General strategy

  • Chunk window predicates. [2018-08-01 Wed 18:29]

    So the story is AST -> FormatTree -> ChunkList.

    A ChunkList is a list of indent-aware chunks of text. Some formatting operations are impractical to attempt in the format tree, such as finding and replacing sequences.

    Here is an example of such an operation, there is an else keyword follow by vertical space and then an if statement. 

    ...
_vspace { depth: 3 }
_vspace { depth: 3 }
_string { depth: 2, str: 'else' }
_vspace { depth: 2 }
_string { depth: 2, str: 'if' }
_hspace { depth: 2 }
_string { depth: 2, str: '(' }
_hspace { depth: 2 }
...

    This just won't do! That if keyword needs to be yanked up next to the else. So, all that's needed is a predicate that can inspect three adjacent chunks at once, matching on [else, vspace, if], and apply a function that changes the vspace to an hspace.

    There will be many such patterns, so the question is, what's the best way to do it? Well.

    • Imagine a collection of rules defined declaratively that are compacted into a state machine. Maybe overkill.
    • 1 Linear traversal? Will need to use a linked list because the number of elements at a particular window location may increase. (really don't want to have to worry about that reality causing a redesign).
    • N linear traversals, (the lazy way) allocating a new list for every predicate. Maybe N is so small that it doesn't matter?

Grouping declarations

Add vspace after groups of declarations.

Types of edits [2018-08-04 Sat 11:27]

edit1.jpg

Figure 1: verilog source from OCW 6.884 Lec.2, p.53

Edits - There are four? types of edits.

  • Tree edits

    Tree edits add and remove structure while walking the AST, they don't inspect parent nodes to determine formatting, but rather focus on adding appropriate white space and indentation.

  • Flat edits

    Flat edits alter chunk lists. If an edit can happen as a tree edit then it should because flat edits involve traversing, matching and rewriting sequences. Any rewrite that depends on line length need to be a flat edit, since indentation isn't known until the tree is flattened.

  • Line edit

    after the all of the other two types of edits are performed, there may be some edits on individual lines with simpler matching 

    if ( ok ) 
  done = 1;

    changes to 

    if ( ok ) done = 1;

    But, still not sure if that's easier as a line edit. It's easy to trim space and check line lengths. But, what if that if block is more than one statement? Check the indentation, ok. But what about more complicated scenarios? Spaghettiville.

Need more flexible indentation [2018-08-09 Thu 12:57]

Here's the problem, the final else clause isn't indented. 

begin
  if ( !running )
    ctrl_sig = 6'b11_00x_0;
  else if ( !B_zero )
    ctrl_sig = 6'b10_1x0_0;
  else
  ctrl_sig = 6'b00_xxx_1;
end

Why? The AST sees it like this: 

(if cond stmt
    (else (if cond stmt
              (else stmt))))

The grammar treats if-elses as nested clauses. Some if the else blocks are blindly indented, then this would happen. 

begin
  if ( !running )
    ctrl_sig = 6'b11_00x_0;
    else if ( !B_zero )
      ctrl_sig = 6'b10_1x0_0;
      else
        ctrl_sig = 6'b00_xxx_1;
end

Approaches [2018-08-09 Thu 14:25]

before going further, start working with a larger source file to really kick the tires on the current all around formatting scheme.

  • Change the grammar?

    no.

  • As tree edit
    • Peek into the else branch while building the format tree? This may be the cleanest way to do it. as long as there are only a few cases. Will checking if the else clauses contains a conditional statment be sufficient?
    • make indented idempotenet: indented(x) = indented(indented(x)).
    • last resort introduce (indent) (undent) directives? that would make "curDepth" a global var, lots of imperative reasoning required.

Line Wrapping [2018-08-16 Thu 22:38]

Still not sure if this is as involved as it seems like it might be. Why? 

wire [31:0] npc_next = reset ? 32'h80000000 : msel ? npc : branch ? { list_of_expressions } :
                       trap ? 32'h80000004 : interrupt ? { list_of_expressions } :
                       { list_of_expressions } ;

needs to transform to 

wire [31:0] npc_next = reset ? 32'h80000000 : 
                       msel ? npc : 
                       branch ? { list_of_expressions } :
                       trap ? 32'h80000004 : interrupt ? { list_of_expressions } :
                       { list_of_expressions } ;

But only wrap at the colon under what conditions exactly?

Approaches

  • As line edit

    introduce a function \(Line \rightarrow [Line]\). Where \(Line :: [Chunk]\)

    However, this function \(f\) needs to be introduced into the (pp) definition. Line wrapping is going to be close to the last actions performed, so \(f\) needs to be passed along through build(), flatten(), and ChunkTransform. Also, this needs to happen before chunks are turned to strings. So next task is to clean up some of the code. Think about either extending PNode or creating a new ChunkNode for the Line edit pass. Write some tests and get this strategy squared away so it can be implemented.

    -—

  • DONE As tree edit

    the nice part of the expressions like: 

    a ? 0 : b ? 1 : c ? ...

    is that they are nested in the AST, so during the flatten() pass, it's possible to get the total length of the ternary operator expression. One the length is known then a better informed decision can be made about wrapping.

More Line Wrapping [2018-08-30 Thu 12:17]

A better solution has appeared!

Define a WrapNode type that extends FmtNode. WrapNode would indicate where a wrap should be considered, but not necessarily needed.

Looking ahead.

Line wrapping requires look-ahead to determine how much text a line has which in turn is used to determine whether or not to line wrap at all. It seems like linewrapping is all or nothing, either wrap or don't, which is nice if true and even nicer if the same holds for recursively descending into expressions on a line.

Looking behind.

I think the scope of concern is contained much like plain indentation, that is, if a long line is being wrapped.

[confused] Does the the formatter have be aware of this, but not necessarily keep track of the a wrapping-depth, since the wrapping logic generally looks backwards the already formatted text to know exactly where to start the next line.

Conclusion

So, Two rules: Look ahead to determine if line wrap is required. Look back to know where to start the next line. Maybe these rules are absolute

Verilog Parser [May 2018]

A hand coded verilog parser, still needs work around error handling.

parser code

Author: Derek Rhodes

Created: 2018-09-19 Wed 17:02