PART 1/3

The lack of open tools is a huge problem. My friends on IRC are working on reverse engineering multiple chips enough that full compilation tool chains can work. My part of the project is working to make a highly generic method of loading the compiled files onto the actual chips no matter the programmer or chip used.

I will expand on the steps of compiling for an FPGA, loading a program onto an FPGA, the difficulties we face in making our own tools, and then talk about my project a little (which cgag was kind enough to name drop). As you can see from the post size this will be very long but should be very educational.

First thing is there are more parts to the bitstream generation, as well as other tools of the toolchain required after bitstream generation is done.

The compilation is split into the following parts.

HDL SYNTHESIS
HDLs can work for both ASIC design, FPGA design, and more general work like some mathematical proofs that never intend to run on real hardware. This step takes in a HDL program and calculates all the gates required. The output is called a netlist is more of a mathematical construct of connections over perfect wires (everything is ideal i.e. not realistic). This step should also detect repeated gate mpatterns in the netlist and de-duplicate them (This is crazy important since it can shrink a netlist substantially). Commonly tools that implement this step will produce everything in one gate type (like NAND http://en.wikipedia.org/wiki/NAND_logic).
There are two major open source tools:
Icarus Verilog (http://iverilog.icarus.com/) used more for the math proofs and simulation but not intended to generate information for real chips.
Yosys (https://github.com/cliffordwolf/yosys) A much newer tool that is made to be part of a real life FPGA toolchain once the next tools are available. Only works with Verilog (more popular in industry).

TECHNOLOGY MAPPING
The link OP posted shows how the FPGA has specialty hardware peppered in with the general gates to speed up certain operations. The link briefly talks about the truth tables in the LUTs which means that each LUT is not really just A gate, they are each a box that can be configured to implement one of many common sequences of gates to save space and speed. Each FPGA can be implemented differently, and since the synthesis step outputs a netlist usually in a specific gate type, the gates of the netlist often do not match the gates that can be efficiently implemented in the LUTs. This tool is the first one that has to have deep knowledge of the FPGA's underlying technology (often called the Fabric) so we can convert the netlist into something that could in theory be put on the target FPGA. Synthesis tools do not implement this step since it is FPGA specific.

PLACE AND ROUTE
After we generate a netlist of realistic gates we have to find out how to fit them into them onto the physical chip with enough room to connect to each other. This by itself is a VERY hard problem and takes most of the time of the full compilation. It is made more difficult by the fact that this requires extremely specific information about the FPGA's fabric to know not only what paths are available, but also make sure that the paths between LUTs are not too slow so we can send signals around the chip fast enough (programs for FPGAs are not like programs for CPUs where each instruction happens one after the other. In an FPGA all the gates are running at the same time so we have to time the electricity running at the speed of light to give the circuits time to execute, and move LUT's around if our timing is not met. This timing happens in a CPU too, but the CPU designer got this working so our instructions run in a predictable way).

BITSTREAM GENERATION
The final step of the compilation toolchain is to take the LUT configuration and routing information from place-and-route and convert it to a binary file the FPGA can actually 'run'. Like Place-and-route this step is highly FPGA dependent. We already know the configuration of the fpga we want from the last step so this step is just converting that configuration into the binary file format for the FPGA. This format is also kept secret.