This is a summary of the Google Summer of Code project MyHDL: Fixed-point Compiler.
The main repository of MyHDL has created a gsoc branch for GSoC projects this year. However, none of the code has been merged in until now.
Summary of Goals
The goals have been described simply in my proposal:
When the project finishes, MyHDL should have a complete implementation of
fixbvand its compiler backend with complete documentation, include tutorials and reference.
It contains 3 parts: front-end, back-end, and documentation. To simply speaking, it is far from saying that the project has been "completed". Although the front-end has been finished, the back-end is still not working, and although I have written many blog posts about my work and the implementation of MyHDL, the documentation of
fixbv interface at this time temporarily is still MEP-111.
Here is a detailed description of each part.
Before my project, cfelton has implemented a simple
fixbv front-end. It only supports some simple functions. So I made the following improvements:
- Added support for Python 3.x.
- Added support for point alignment.
- Added support for round modes and overflow modes.
- Added more tests for
These improvements made an almost complete change on the previous
fixbv implementation, and also affected some other critical code, such as
It has only some minor issues left now. Because those issues do not affect the core function of
fixbv, the implementation of these issues has been put in a lower priority after discussion with mentors.
- There are still some minor issues marked as
@todoafter cleaned up cfelton's code.
- Implementation of
fxsumwhich is described in a previous post. Since it only affects intermediate results, it seems not necessary.
- Interoperability with
intbvcould be treated as a
fixbvwithout a fractional part, it is possible to operate between
fixbv. It has been given a low priority since it is not defined in MEP-111 and not so emergent at this time.
At this time, only the tests of Verilog conversion has been implemented. There are a few patches on the back-end code but it is still not working even with those simple test cases.
There are still something that needs to go:
- Patch AST node visitors for conversion.
- Patch other parts of the back-end code in order to implement all the functions of
- Make bigger test cases to better check the implementation, such as CORDIC.
Until now, the main documentation of
fixbv is MEP-111 of MyHDL project, which is written by cfelton.
I have written some blog posts of some features and issues of
fixbv. However, this part has not been merged into a larger documentation. It will be helpful in the future.
Reasons of Incomplete
- The plan is too ambitious. I thought it was just a new type on this existing platform. However, I should also review many other parts of work according to different issues that may take.
- Too much hanging around in the ad hoc issues. While implementing the front-end, there were so many small issues and I have to take time to fix them.
- Not enough work time. GSoC needs 40 hours per week to work for the project. However, I am in a university located in Japan, and I have to deal with final exams in June and August for spring and summer quarter respectively. It took me a lot of time. I have suggested future GSoC to consider students' time in different regions.
- Fully implement the back-end with tests.
- Merge the documentation to some places like The MyHDL Manual.
- Implement interoperability between
I have deeply involved in the society of MyHDL. I will contribute to it in the future.
In MyHDL source code, "front-end" means the simulation part, and "back-end" usually means the conversion (MyHDL to Verilog or VHDL) part. The code of conversion part is in
myhdl/conversion path, while the unit tests are in
First, let's see
myhdl/conversion/__init__.py in this directory about what it provides to users:
This is rather simple. The most useful things we provide are
toVHDL. If you don't know about the usage of these methods, please refer to related contents in MyHDL documentation.
Also, we could see that the function
analyze does not come from
_analyze.py. Instead, it comes from
_verify.py. The reason will be explained in later posts for
_misc.py, some helper functions are provided. It is better to examine them when we need them.
What Do We Call When We Call
Let's get a head start of the whole back-end from
_toVerilog.py. We can see that in
__init__.py, it imports a
toVerilog object in Verilog. So, what is
_toVerilog.py, we could find a line of its definition:
So it is an instance of
In the definition of
_ToVerilogConvertor, it has four methods:
_convert_filter. The last two methods are helpers for the code in
__call__. We can ignore them at this time.
myhdl, the previously mentioned
toVerilog = _ToVerilogConvertor() will be executed, so that
_ToVerilogConvertor.__init__ will be called at this time. When user code calls
toVerilog such as
toVerilog(...), it is actually
_ToVerilogConvertor.__call__(...). So, even though
toVerilog looks like a function while using, it is actually implemented by the class
We could see a lot of examples of this kind of design pattern.
_ToVerilogConvertor.__init__, it only defines some necessary attributes for conversion. It is similar to
_ToVerilogConvertor.__call__, the code is longer, so some necessary checks and initializations will be skipped in the analysis. It works as following steps:
This method first defines the file name and its path, and open it as a file called
It extracts a flattened list of arguments of the whole hierarchy. Also a list of signals and a list of generators will be analyzed. And then, it infers the interface of the top module.
It extracts document string from the top level by calling
inspectmodule, which is a default module in Python.
It writes the file header, the module header, the signal declarations in
vfileby using the extracted interface and the list of signals above.
It converts generators to Verilog code by visiting the abstract syntax tree (AST) of it. The conversion from Python code to AST is done by the module
ast, which is provided in the default Python implementation. The Verilog code will be written into
It writes the module footer
If the test bench is valid for the code, it will also converts the test bench into Verilog.
It builds a port map from the interface for co-simulation.
Note: If you don't know what an AST is, please refer to here as a tutorial. This concept is very important in MyHDL back-end.
Functions provided in
_analyze.py is heavily used in
_ToVerilogConvertor.__call__. Some other code, even if they are not in
myhdl/conversion, are called in the implementation. So, if you want to make every details clear, it is necessary to read the code of the whole project.
Walking Through AST
To see how AST has been walked through, it is better to take a look at method
_convertGens at first. It uses with different visitors when the tree is in different kinds of blocks, like
always_seq, etc. However, all of these visitors are derived from
_ConvertVisitor, with only a few differences.
_ConvertVisitor is derived from
ast.NodeVisitor. We could see that it has different types of methods for visiting different types of AST nodes. The visitor will walk through the tree by using these methods.
Since there is already many types of AST nodes, and the code is not difficult, it is recommended to read the code and see what does the convertor do during visiting different kinds of nodes if you are interested in it.
For the documentation of different types of nodes, please refer to Green Tree Snake.
Comparing to round modes I introduced in the last post, overflow modes are rather simple.
There are only 3 overflow modes in cfelton's
saturate means that if overflow occurs, the value will remain maximum (minimum if underflow).
wrap behaves the same. If overflow occurs, it then builds up from minimum. Similarly, if underflow occurs, it goes down from maximum. For binary implementation, it is just reserve the last bits in its width.
We can see clearly in the original implementation:
In cfelton's implementation of
fixbv, there are some kinds of round modes implemented in
_resize.py, as in the source code:
The behavior of
floor is quite clear in this case. Whatever fractional part is, it will be rounded to the integer towards +inf, 0, or -inf.
But it seems not quite clear for the last four modes.
OK, let's see the source code in
To read the last 4 kinds of resolution, it is necessary to know the behavior of Python's built-in
Here we assume we do not provide
ndigits parameter to
Python's document says that
round will round the numbers to the nearest integer. However, if the fractional part is 0.5,
round will round to the nearest even number. That is to say,
round(2.5) will be 2, but
round(3.5) will be 4.
So, I guess that the behavior of round modes
convergent are the same.
nearest will be the same as the above three round modes in negative values, but for positive values, it will be different. If the fractional part is 0.5, it will advance to the larger integer, otherwise round to the nearest.
To verify this, I wrote a small program for it. The rounding code is copied from corresponding function in
It tests different values for different round modes.
Here is the result:
EDIT: The code of "nearest" rounding did not handle the case of negative values, so the condition case should be:
And its behavior when the fractional part is 0.5 (either positive or negative) should be rounding away from 0.
If you want to sum up several
fixbv fixed-point variables, what will you do?
If your answer is as follows:
It seems to be correct but there would be a trap on the bit width.
Bit Width Changing While Adding
Here we use
(total_width, integer_width, fractional_width) to indicate the bit width of the
fixbv variable, its integer part, and its fractional part.
As written in MEP-111, if two fixed-point variables are added, the fractional part of the result should be the longest of the operands; and the integer part of the result should be the longest plus one, in order to avoid overflow.
This is an example of adding a variable in format
(8, 3, 4) and another variable in format
(8, 0, 7):
We can see that the first operand has been added zeros in the tail of the fractional part, and the second operand has been added sign bits in the beginning, in order to perform point alignment.
A Critical Example
Considering the following situation:
If we add like
a + b + c + d, the format of the final result will be:
However, if we add in
d + a + b + c, the result should be:
If we use the assignment like:
this problem should be consider. But, if we have already defined the format of x and perform the operation as
it would be safer because the format of
x has already been decided. However, rounding and overflow must be considered if necessary.
A New Sum Function for Fixed-Point Variables
So here, in order to make the result unique in different orders, a new function
fxsum is needed in this theme. The usage is similar to built-in
fxsum requires an iterable parameter containing
fixbv instances, and returns the sum as a
fixbv variable. The width of the fractional part would be the longest in the iterable, while the width of the width of the integer part is the longest plus
ceil(log(N, 2)), in which
N is the width of the longest integer part.
Instead of using
a + b + c + d, we could write
to avoid ambiguity of bit width in the result.
As a result, in the previous example, we could obtain that
which is the optimal format in the worst case.
In the previous post, I thought the point alignment of
fixbv should be implemented in a short time. Soon I found myself wrong.
After fixing a compatibility bug in the unit test
test_fixbv.py, the problem of point alignment has been revealed.
If point alignment only solved in
_fixbv.py, in the case of a variable of
Signal plus or minus a variable of
fixbv, MyHDL simulator will throw a problem. So I have to implement both in
fixbv.__add__. Also, I have to consider if they plus or minus
So, it causes a problem of cross import. I posted this StackOverflow question and you may see the implementation.
Temporarily, my solution is (in
This implementation only considered
Signal. However, if I consider
intbv, things might be more complex.
It leaves a question I am going to solve now.
I should say "Long time no see" since I have not written blogs since about 2 or 3 weeks ago. Sorry for that.
The first evaluation is coming soon. I hope my blog would make it.
Related Source Code
All the progress of this project can be checked in these problems.
The front end of
fixbv (the part for MyHDL simulation usage) has been roughly implemented by cfelton. Although it has some issues, I may adopt it as a good start.
There are some issues in cfelton's implementation:
- At his time of implementation, MyHDL supports only Python 2.x. So the compatibility between 2.x and 3.x has not been considered.
- Compiler backend has not been implemented.
overflow_modewere not implemented.
- Point alignment has not been implemented.
- Many places marked as
@todo. Most of them are small problems.
I planned to solve the above issues except 2 before the beginning of July.
Python 3.x Compatibility
Conversion is the core issue of this project. Before advancing into this phase, I must solve other issues first.
I am planning to do it in July and August.
Round Mode and Overflow Mode
To be decided.
Should it also be considered while implementing compiler backend?
Other Small Problems
In July, I will implement the compiler backend of
In the first 2 weeks of July, I will write conversion tests for
fixbv. After that, I will implement the backend of
fixbv and write documents for it.
In mid August, this project should be finished.
To make full use of MyHDL, it is strongly recommended to install and configure cosimulation modules. So that the output (Verilog/VHDL code) of MyHDL compiler backend can be evaluated, and the current MyHDL code can work with the conventional code base and migrate into industrial EDA workflow.
At this time, only Verilog users have to install it for cosimulation. So that we can use
to_myhdl in our example.
Here, I assume that MyHDL has been installed by the steps in the previous post.
Installing Icarus Verilog
MyHDL supports several popular RTL simulators. At this time, Icarus Verilog, GHDL, cver, and ModelSim were supported. Here, Icarus Verilog will be used as an example.
Icarus Verilog is already in some Linux distributions. For example, in Ubuntu, type the following command to install Icarus Verilog:
For Windows users, Windows binaries might be useful.
VPI module provides an interface for Verilog to share data with MyHDL.
Compiling VPI module
In the source code of MyHDL, the
cosimulation folder contains several types of simulator that supported. In each subfolder, the README file describes how to install MyHDL support for these simulators.
For Icarus Verilog, go to
cosimulation/icarus, and then use command
make to compile the vpi module. Then, you will get
myhdl.vpi after compiling.
You can copy
myhdl.vpi to other places while needed.
Follow cosimulation chapter of the manual could also make sense, especially when you want to get a direct message of why the cosimulation does not work.
Please refer to corresponding manpages to get the meanings of options for
Notes on Windows Installation
The process of Windows installation is almost the same, but there are still some difference. Here are the notes that may help your installation.
After installing iverilog, remember to add the path of
iverilog-vpi.exeto the system path.
Before compiling VPI files, a MinGW implementation should be installed and added into system path.
When compiling VPI modules,
myhdl.cwill probably be overwritten and fail to compile. If this situation occurs, please replace
myhdl.cwith the original one, and then copy the
myhdl_table.cto the end of
myhdl.c, and then execute
The first step to get involved in the development MyHDL is to set up the environment. In this blog post, I will introduce the development environment.
Before reading these files, I assume you should have a basic knowledge of Python, Git, and MyHDL.
Step 0: Prerequisites
The software prerequisites of developing MyHDL is quite simple: Python and Git. If you want to do cosimulation, you may need a VHDL/Verilog simulator supported by MyHDL.
There are bunches of tutorials on the Internet that teach you how to install Python and Git. You can search them for detailed instructions of installation. Here is just a reminder.
Also, a GitHub account is required.
For MyHDL development, the version of Python should be at least 2.6 for 2.x versions and at least 3.4 for Python 3.x. Personally, I prefer Python 3.x, but it doesn't matter which version you use for developing. For compatibility purpose, the code should treat 2.x and 3.x equally.
On Linux distributions, you can install from either package repositories or source code.
For example, you may execute the following command on Ubuntu to install from software repo:
On Windows, you can download directly from the official website of Python. Or you can also download Python distributions such as Anaconda since it contains more tools especially for science and Engineering.
On Linux distributions, you can install git from software repository. For example, in Ubuntu, you may execute the following command:
For Windows and Mac users, GitHub Desktop is recommended.
You may find the book Pro Git useful when you using git command line.
My blog posts will mainly introduce operations in command line. If you prefer GitHub Desktop, you may find the user interface very friendly and very easy to do equivalent work as in command line. But the git command line is more extensive.
Register and configure GitHub account
Please follow the related documents in GitHub Help.
Also, it is nice to configure git by following the related section of Pro Git. Especially, configuring text editor using in git is recommended.
Step 1: Fork the repo
The main repository of MyHDL is on GitHub.
In MyHDL repository page, click "Fork" button, which is located on the upper right corner of the page. Then, the page will jump to your own repository forked before.
Forking a repo on GitHub is like to create your own copy of the project. You may make changes on your own repo and make pull requests to contribute back to the original project.
Step 2: Clone the repo to your own computer
Now, you are in your own repo.
Click "Clone or download" button, and the URL will pop up. Copy this URL to the clipboard.
In the working directory of your local computer, execute the following command: (Please change "qrqiuren" to your own user name)
Then, you will see a subfolder called
myhdl is created. It is your git repository.
Execute the following command to change the current directory to
Add the upstream as a remote would be easier to keep up with upstream in later development.
Step 3: Setup MyHDL in developer mode
You may need
setuptools to setup in developer mode. In Ubuntu, install
Execute the following command to setup MyHDL in developer mode
If you have read the README file, you may find that I have replaced
develop in the command. That is because if I use
develop, and changed the code in
myhdl directory, the changes will immediately affect other Python programs that import
myhdl. This is very useful when you change the code frequently.
Installation of cosimulation modules
Please refer to GSoC #2: Configuration of Cosimulation.
Run unit tests
It will start running unit tests. If there is any problems, maybe the installation or the code is not correct.
Step 4: Contribute
In order not to mix with other code, you should work on a new branch instead of
master. For example, if you want to add a branch to implement MEP-111 specified in the website of MyHDL, you should switch to this branch by using
And then, you can make the commits while remaining the main branch unaffected.
Now, it is time to review the code and contribute to it.
After you make some changes in the code, you may have to commit it. Execute the following command to see what you have done since last commit
Now, you can add the changed files to the buffer to prepare for the next commit. For example, if you changed some code in
myhdl/_intbv.py, you may execute
After you added all the files, you can commit to the git database by using
Then, a text editor (as configured before) will be opened for you to edit the commit message. You should briefly write what you have done in this commit, preferrably in one sentence. Please note that usually commits in git should be as "atomic" as possible, which means one commit does only one thing and cannot be separated anymore.
Finally, if you want to push the local git database to GitHub, you should execute the following:
Writing unit tests
It is required to write corresponding unit tests if you modified the code. You may put your unit tests to the corresponding subfolder in
Please refer to Writing Tests for a guide to write unit tests for MyHDL.
Step 5: Make a pull request
A pull request (PR) is a way to request contributing the code from your repo to the original repo.
Before making a PR
Here is a simple checklist before making a PR:
- Have you committed all the code that consist this PR?
- Have you written unit tests for it?
Make a pull request
Go to the GitHub page of the forked repository.
Click "New pull request" button, and then submit the information about this pull request. Then, the PR will be created.
For more information of making a pull request, please refer to GitHub help.
It is exciting to announce that my proposal MyHDL: Fixed-point Compiler has been accepted as a project of Google Summer of Code.
From now on, I will start blogging in English on this site. I will write about the progress of my project and studies on MyHDL. For progress, please checkout the GSoC tag of this blog. Related code will be on my GitHub repo.
Code speaks louder than words. Then, let's get started.