diff options
Diffstat (limited to 'docs/source/CHAPTER_Basics.rst')
| -rw-r--r-- | docs/source/CHAPTER_Basics.rst | 776 |
1 files changed, 776 insertions, 0 deletions
diff --git a/docs/source/CHAPTER_Basics.rst b/docs/source/CHAPTER_Basics.rst new file mode 100644 index 000000000..618bec545 --- /dev/null +++ b/docs/source/CHAPTER_Basics.rst @@ -0,0 +1,776 @@ +.. role:: verilog(code) + :language: Verilog + +.. _chapter:basics: + +Basic principles +================ + +This chapter contains a short introduction to the basic principles of digital +circuit synthesis. + +Levels of abstraction +--------------------- + +Digital circuits can be represented at different levels of abstraction. During +the design process a circuit is usually first specified using a higher level +abstraction. Implementation can then be understood as finding a functionally +equivalent representation at a lower abstraction level. When this is done +automatically using software, the term synthesis is used. + +So synthesis is the automatic conversion of a high-level representation of a +circuit to a functionally equivalent low-level representation of a circuit. +:numref:`Figure %s <fig:Basics_abstractions>` lists the different levels of +abstraction and how they relate to different kinds of synthesis. + +.. figure:: ../images/basics_abstractions.* + :class: width-helper + :name: fig:Basics_abstractions + + Different levels of abstraction and synthesis. + +Regardless of the way a lower level representation of a circuit is obtained +(synthesis or manual design), the lower level representation is usually verified +by comparing simulation results of the lower level and the higher level +representation [1]_. Therefore even if no synthesis is used, there must still +be a simulatable representation of the circuit in all levels to allow for +verification of the design. + +Note: The exact meaning of terminology such as "High-Level" is of course not +fixed over time. For example the HDL "ABEL" was first introduced in 1985 as "A +High-Level Design Language for Programmable Logic Devices" :cite:p:`ABEL`, but +would not be considered a "High-Level Language" today. + +System level +~~~~~~~~~~~~ + +The System Level abstraction of a system only looks at its biggest building +blocks like CPUs and computing cores. At this level the circuit is usually +described using traditional programming languages like C/C++ or Matlab. +Sometimes special software libraries are used that are aimed at simulation +circuits on the system level, such as SystemC. + +Usually no synthesis tools are used to automatically transform a system level +representation of a circuit to a lower-level representation. But system level +design tools exist that can be used to connect system level building blocks. + +The IEEE 1685-2009 standard defines the IP-XACT file format that can be used to +represent designs on the system level and building blocks that can be used in +such system level designs. :cite:p:`IP-XACT` + +High level +~~~~~~~~~~ + +The high-level abstraction of a system (sometimes referred to as algorithmic +level) is also often represented using traditional programming languages, but +with a reduced feature set. For example when representing a design at the high +level abstraction in C, pointers can only be used to mimic concepts that can be +found in hardware, such as memory interfaces. Full featured dynamic memory +management is not allowed as it has no corresponding concept in digital +circuits. + +Tools exist to synthesize high level code (usually in the form of C/C++/SystemC +code with additional metadata) to behavioural HDL code (usually in the form of +Verilog or VHDL code). Aside from the many commercial tools for high level +synthesis there are also a number of FOSS tools for high level synthesis . + +Behavioural level +~~~~~~~~~~~~~~~~~ + +At the behavioural abstraction level a language aimed at hardware description +such as Verilog or VHDL is used to describe the circuit, but so-called +behavioural modelling is used in at least part of the circuit description. In +behavioural modelling there must be a language feature that allows for +imperative programming to be used to describe data paths and registers. This is +the always-block in Verilog and the process-block in VHDL. + +In behavioural modelling, code fragments are provided together with a +sensitivity list; a list of signals and conditions. In simulation, the code +fragment is executed whenever a signal in the sensitivity list changes its value +or a condition in the sensitivity list is triggered. A synthesis tool must be +able to transfer this representation into an appropriate datapath followed by +the appropriate types of register. + +For example consider the following Verilog code fragment: + +.. code:: verilog + :number-lines: + + always @(posedge clk) + y <= a + b; + +In simulation the statement ``y <= a + b`` is executed whenever a positive edge +on the signal ``clk`` is detected. The synthesis result however will contain an +adder that calculates the sum ``a + b`` all the time, followed by a d-type +flip-flop with the adder output on its D-input and the signal ``y`` on its +Q-output. + +Usually the imperative code fragments used in behavioural modelling can contain +statements for conditional execution (``if``- and ``case``-statements in +Verilog) as well as loops, as long as those loops can be completely unrolled. + +Interestingly there seems to be no other FOSS Tool that is capable of performing +Verilog or VHDL behavioural syntheses besides Yosys. + +Register-Transfer Level (RTL) +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +On the Register-Transfer Level the design is represented by combinatorial data +paths and registers (usually d-type flip flops). The following Verilog code +fragment is equivalent to the previous Verilog example, but is in RTL +representation: + +.. code:: verilog + :number-lines: + + assign tmp = a + b; // combinatorial data path + + always @(posedge clk) // register + y <= tmp; + +A design in RTL representation is usually stored using HDLs like Verilog and +VHDL. But only a very limited subset of features is used, namely minimalistic +always-blocks (Verilog) or process-blocks (VHDL) that model the register type +used and unconditional assignments for the datapath logic. The use of HDLs on +this level simplifies simulation as no additional tools are required to simulate +a design in RTL representation. + +Many optimizations and analyses can be performed best at the RTL level. Examples +include FSM detection and optimization, identification of memories or other +larger building blocks and identification of shareable resources. + +Note that RTL is the first abstraction level in which the circuit is represented +as a graph of circuit elements (registers and combinatorial cells) and signals. +Such a graph, when encoded as list of cells and connections, is called a +netlist. + +RTL synthesis is easy as each circuit node element in the netlist can simply be +replaced with an equivalent gate-level circuit. However, usually the term RTL +synthesis does not only refer to synthesizing an RTL netlist to a gate level +netlist but also to performing a number of highly sophisticated optimizations +within the RTL representation, such as the examples listed above. + +A number of FOSS tools exist that can perform isolated tasks within the domain +of RTL synthesis steps. But there seems to be no FOSS tool that covers a wide +range of RTL synthesis operations. + +Logical gate level +~~~~~~~~~~~~~~~~~~ + +At the logical gate level the design is represented by a netlist that uses only +cells from a small number of single-bit cells, such as basic logic gates (AND, +OR, NOT, XOR, etc.) and registers (usually D-Type Flip-flops). + +A number of netlist formats exists that can be used on this level, e.g. the +Electronic Design Interchange Format (EDIF), but for ease of simulation often a +HDL netlist is used. The latter is a HDL file (Verilog or VHDL) that only uses +the most basic language constructs for instantiation and connecting of cells. + +There are two challenges in logic synthesis: First finding opportunities for +optimizations within the gate level netlist and second the optimal (or at least +good) mapping of the logic gate netlist to an equivalent netlist of physically +available gate types. + +The simplest approach to logic synthesis is two-level logic synthesis, where a +logic function is converted into a sum-of-products representation, e.g. using a +Karnaugh map. This is a simple approach, but has exponential worst-case effort +and cannot make efficient use of physical gates other than AND/NAND-, OR/NOR- +and NOT-Gates. + +Therefore modern logic synthesis tools utilize much more complicated multi-level +logic synthesis algorithms :cite:p:`MultiLevelLogicSynth`. Most of these +algorithms convert the logic function to a Binary-Decision-Diagram (BDD) or +And-Inverter-Graph (AIG) and work from that representation. The former has the +advantage that it has a unique normalized form. The latter has much better worst +case performance and is therefore better suited for the synthesis of large logic +functions. + +Good FOSS tools exists for multi-level logic synthesis . + +Yosys contains basic logic synthesis functionality but can also use ABC for the +logic synthesis step. Using ABC is recommended. + +Physical gate level +~~~~~~~~~~~~~~~~~~~ + +On the physical gate level only gates are used that are physically available on +the target architecture. In some cases this may only be NAND, NOR and NOT gates +as well as D-Type registers. In other cases this might include cells that are +more complex than the cells used at the logical gate level (e.g. complete +half-adders). In the case of an FPGA-based design the physical gate level +representation is a netlist of LUTs with optional output registers, as these are +the basic building blocks of FPGA logic cells. + +For the synthesis tool chain this abstraction is usually the lowest level. In +case of an ASIC-based design the cell library might contain further information +on how the physical cells map to individual switches (transistors). + +Switch level +~~~~~~~~~~~~ + +A switch level representation of a circuit is a netlist utilizing single +transistors as cells. Switch level modelling is possible in Verilog and VHDL, +but is seldom used in modern designs, as in modern digital ASIC or FPGA flows +the physical gates are considered the atomic build blocks of the logic circuit. + +Yosys +~~~~~ + +Yosys is a Verilog HDL synthesis tool. This means that it takes a behavioural +design description as input and generates an RTL, logical gate or physical gate +level description of the design as output. Yosys' main strengths are behavioural +and RTL synthesis. A wide range of commands (synthesis passes) exist within +Yosys that can be used to perform a wide range of synthesis tasks within the +domain of behavioural, rtl and logic synthesis. Yosys is designed to be +extensible and therefore is a good basis for implementing custom synthesis tools +for specialised tasks. + +Features of synthesizable Verilog +--------------------------------- + +The subset of Verilog :cite:p:`Verilog2005` that is synthesizable is specified +in a separate IEEE standards document, the IEEE standard 1364.1-2002 +:cite:p:`VerilogSynth`. This standard also describes how certain language +constructs are to be interpreted in the scope of synthesis. + +This section provides a quick overview of the most important features of +synthesizable Verilog, structured in order of increasing complexity. + +Structural Verilog +~~~~~~~~~~~~~~~~~~ + +Structural Verilog (also known as Verilog Netlists) is a Netlist in Verilog +syntax. Only the following language constructs are used in this +case: + +- Constant values +- Wire and port declarations +- Static assignments of signals to other signals +- Cell instantiations + +Many tools (especially at the back end of the synthesis chain) only support +structural Verilog as input. ABC is an example of such a tool. Unfortunately +there is no standard specifying what Structural Verilog actually is, leading to +some confusion about what syntax constructs are supported in structural Verilog +when it comes to features such as attributes or multi-bit signals. + +Expressions in Verilog +~~~~~~~~~~~~~~~~~~~~~~ + +In all situations where Verilog accepts a constant value or signal name, +expressions using arithmetic operations such as ``+``, ``-`` and ``*``, boolean +operations such as ``&`` (AND), ``|`` (OR) and ``^`` (XOR) and many others +(comparison operations, unary operator, etc.) can also be used. + +During synthesis these operators are replaced by cells that implement the +respective function. + +Many FOSS tools that claim to be able to process Verilog in fact only support +basic structural Verilog and simple expressions. Yosys can be used to convert +full featured synthesizable Verilog to this simpler subset, thus enabling such +applications to be used with a richer set of Verilog features. + +Behavioural modelling +~~~~~~~~~~~~~~~~~~~~~ + +Code that utilizes the Verilog always statement is using Behavioural Modelling. +In behavioural modelling, a circuit is described by means of imperative program +code that is executed on certain events, namely any change, a rising edge, or a +falling edge of a signal. This is a very flexible construct during simulation +but is only synthesizable when one +of the following is modelled: + +- | **Asynchronous or latched logic** + | In this case the sensitivity list must contain all expressions that + are used within the always block. The syntax ``@*`` can be used for + these cases. Examples of this kind include: + + .. code:: verilog + :number-lines: + + // asynchronous + always @* begin + if (add_mode) + y <= a + b; + else + y <= a - b; + end + + // latched + always @* begin + if (!hold) + y <= a + b; + end + + Note that latched logic is often considered bad style and in many + cases just the result of sloppy HDL design. Therefore many synthesis + tools generate warnings whenever latched logic is generated. + +- | **Synchronous logic (with optional synchronous reset)** + | This is logic with d-type flip-flops on the output. In this case + the sensitivity list must only contain the respective clock edge. + Example: + + .. code:: verilog + :number-lines: + + // counter with synchronous reset + always @(posedge clk) begin + if (reset) + y <= 0; + else + y <= y + 1; + end + +- | **Synchronous logic with asynchronous reset** + | This is logic with d-type flip-flops with asynchronous resets on + the output. In this case the sensitivity list must only contain the + respective clock and reset edges. The values assigned in the reset + branch must be constant. Example: + + .. code:: verilog + :number-lines: + + // counter with asynchronous reset + always @(posedge clk, posedge reset) begin + if (reset) + y <= 0; + else + y <= y + 1; + end + +Many synthesis tools support a wider subset of flip-flops that can be modelled +using always-statements (including Yosys). But only the ones listed above are +covered by the Verilog synthesis standard and when writing new designs one +should limit herself or himself to these cases. + +In behavioural modelling, blocking assignments (=) and non-blocking assignments +(<=) can be used. The concept of blocking vs. non-blocking assignment is one of +the most misunderstood constructs in Verilog :cite:p:`Cummings00`. + +The blocking assignment behaves exactly like an assignment in any imperative +programming language, while with the non-blocking assignment the right hand side +of the assignment is evaluated immediately but the actual update of the left +hand side register is delayed until the end of the time-step. For example the +Verilog code ``a <= b; b <= a;`` exchanges the values of the two registers. + + +Functions and tasks +~~~~~~~~~~~~~~~~~~~ + +Verilog supports Functions and Tasks to bundle statements that are used in +multiple places (similar to Procedures in imperative programming). Both +constructs can be implemented easily by substituting the function/task-call with +the body of the function or task. + +Conditionals, loops and generate-statements +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +Verilog supports ``if-else``-statements and ``for``-loops inside +``always``-statements. + +It also supports both features in ``generate``-statements on the module level. +This can be used to selectively enable or disable parts of the module based on +the module parameters (``if-else``) or to generate a set of similar subcircuits +(``for``). + +While the ``if-else``-statement inside an always-block is part of behavioural +modelling, the three other cases are (at least for a synthesis tool) part of a +built-in macro processor. Therefore it must be possible for the synthesis tool +to completely unroll all loops and evaluate the condition in all +``if-else``-statement in ``generate``-statements using const-folding.. + +Arrays and memories +~~~~~~~~~~~~~~~~~~~ + +Verilog supports arrays. This is in general a synthesizable language feature. In +most cases arrays can be synthesized by generating addressable memories. +However, when complex or asynchronous access patterns are used, it is not +possible to model an array as memory. In these cases the array must be modelled +using individual signals for each word and all accesses to the array must be +implemented using large multiplexers. + +In some cases it would be possible to model an array using memories, but it is +not desired. Consider the following delay circuit: + +.. code:: verilog + :number-lines: + + module (clk, in_data, out_data); + + parameter BITS = 8; + parameter STAGES = 4; + + input clk; + input [BITS-1:0] in_data; + output [BITS-1:0] out_data; + reg [BITS-1:0] ffs [STAGES-1:0]; + + integer i; + always @(posedge clk) begin + ffs[0] <= in_data; + for (i = 1; i < STAGES; i = i+1) + ffs[i] <= ffs[i-1]; + end + + assign out_data = ffs[STAGES-1]; + + endmodule + +This could be implemented using an addressable memory with STAGES input and +output ports. A better implementation would be to use a simple chain of +flip-flops (a so-called shift register). This better implementation can either +be obtained by first creating a memory-based implementation and then optimizing +it based on the static address signals for all ports or directly identifying +such situations in the language front end and converting all memory accesses to +direct accesses to the correct signals. + +Challenges in digital circuit synthesis +--------------------------------------- + +This section summarizes the most important challenges in digital circuit +synthesis. Tools can be characterized by how well they address these topics. + +Standards compliance +~~~~~~~~~~~~~~~~~~~~ + +The most important challenge is compliance with the HDL standards in question +(in case of Verilog the IEEE Standards 1364.1-2002 and 1364-2005). This can be +broken down in two items: + +- Completeness of implementation of the standard +- Correctness of implementation of the standard + +Completeness is mostly important to guarantee compatibility with existing HDL +code. Once a design has been verified and tested, HDL designers are very +reluctant regarding changes to the design, even if it is only about a few minor +changes to work around a missing feature in a new synthesis tool. + +Correctness is crucial. In some areas this is obvious (such as correct synthesis +of basic behavioural models). But it is also crucial for the areas that concern +minor details of the standard, such as the exact rules for handling signed +expressions, even when the HDL code does not target different synthesis tools. +This is because (unlike software source code that is only processed by +compilers), in most design flows HDL code is not only processed by the synthesis +tool but also by one or more simulators and sometimes even a formal verification +tool. It is key for this verification process that all these tools use the same +interpretation for the HDL code. + +Optimizations +~~~~~~~~~~~~~ + +Generally it is hard to give a one-dimensional description of how well a +synthesis tool optimizes the design. First of all because not all optimizations +are applicable to all designs and all synthesis tasks. Some optimizations work +(best) on a coarse-grained level (with complex cells such as adders or +multipliers) and others work (best) on a fine-grained level (single bit gates). +Some optimizations target area and others target speed. Some work well on large +designs while others don't scale well and can only be applied to small designs. + +A good tool is capable of applying a wide range of optimizations at different +levels of abstraction and gives the designer control over which optimizations +are performed (or skipped) and what the optimization goals are. + +Technology mapping +~~~~~~~~~~~~~~~~~~ + +Technology mapping is the process of converting the design into a netlist of +cells that are available in the target architecture. In an ASIC flow this might +be the process-specific cell library provided by the fab. In an FPGA flow this +might be LUT cells as well as special function units such as dedicated +multipliers. In a coarse-grain flow this might even be more complex special +function units. + +An open and vendor independent tool is especially of interest if it supports a +wide range of different types of target architectures. + +Script-based synthesis flows +---------------------------- + +A digital design is usually started by implementing a high-level or system-level +simulation of the desired function. This description is then manually +transformed (or re-implemented) into a synthesizable lower-level description +(usually at the behavioural level) and the equivalence of the two +representations is verified by simulating both and comparing the simulation +results. + +Then the synthesizable description is transformed to lower-level representations +using a series of tools and the results are again verified using simulation. +This process is illustrated in :numref:`Fig. %s <fig:Basics_flow>`. + +.. figure:: ../images/basics_flow.* + :class: width-helper + :name: fig:Basics_flow + + Typical design flow. Green boxes represent manually created models. + Orange boxes represent modesl generated by synthesis tools. + + +In this example the System Level Model and the Behavioural Model are both +manually written design files. After the equivalence of system level model and +behavioural model has been verified, the lower level representations of the +design can be generated using synthesis tools. Finally the RTL Model and the +Gate-Level Model are verified and the design process is finished. + +However, in any real-world design effort there will be multiple iterations for +this design process. The reason for this can be the late change of a design +requirement or the fact that the analysis of a low-abstraction model +(e.g. gate-level timing analysis) revealed that a design change is required in +order to meet the design requirements (e.g. maximum possible clock speed). + +Whenever the behavioural model or the system level model is changed their +equivalence must be re-verified by re-running the simulations and comparing the +results. Whenever the behavioural model is changed the synthesis must be re-run +and the synthesis results must be re-verified. + +In order to guarantee reproducibility it is important to be able to re-run all +automatic steps in a design project with a fixed set of settings easily. Because +of this, usually all programs used in a synthesis flow can be controlled using +scripts. This means that all functions are available via text commands. When +such a tool provides a GUI, this is complementary to, and not instead of, a +command line interface. + +Usually a synthesis flow in an UNIX/Linux environment would be controlled by a +shell script that calls all required tools (synthesis and +simulation/verification in this example) in the correct order. Each of these +tools would be called with a script file containing commands for the respective +tool. All settings required for the tool would be provided by these script files +so that no manual interaction would be necessary. These script files are +considered design sources and should be kept under version control just like the +source code of the system level and the behavioural model. + +Methods from compiler design +---------------------------- + +Some parts of synthesis tools involve problem domains that are traditionally +known from compiler design. This section addresses some of these domains. + +Lexing and parsing +~~~~~~~~~~~~~~~~~~ + +The best known concepts from compiler design are probably lexing and parsing. +These are two methods that together can be used to process complex computer +languages easily. :cite:p:`Dragonbook` + +A lexer consumes single characters from the input and generates a stream of +lexical tokens that consist of a type and a value. For example the Verilog input +:verilog:`assign foo = bar + 42;` might be translated by the lexer to the list +of lexical tokens given in :numref:`Tab. %s <tab:Basics_tokens>`. + +.. table:: Exemplary token list for the statement :verilog:`assign foo = bar + 42;` + :name: tab:Basics_tokens + + ============== =============== + Token-Type Token-Value + ============== =============== + TOK_ASSIGN \- + TOK_IDENTIFIER "foo" + TOK_EQ \- + TOK_IDENTIFIER "bar" + TOK_PLUS \- + TOK_NUMBER 42 + TOK_SEMICOLON \- + ============== =============== + +The lexer is usually generated by a lexer generator (e.g. flex ) from a +description file that is using regular expressions to specify the text pattern +that should match the individual tokens. + +The lexer is also responsible for skipping ignored characters (such as +whitespace outside string constants and comments in the case of Verilog) and +converting the original text snippet to a token value. + +Note that individual keywords use different token types (instead of a keyword +type with different token values). This is because the parser usually can only +use the Token-Type to make a decision on the grammatical role of a token. + +The parser then transforms the list of tokens into a parse tree that closely +resembles the productions from the computer languages grammar. As the lexer, the +parser is also typically generated by a code generator (e.g. bison ) from a +grammar description in Backus-Naur Form (BNF). + +Let's consider the following BNF (in Bison syntax): + +.. code:: none + :number-lines: + + assign_stmt: TOK_ASSIGN TOK_IDENTIFIER TOK_EQ expr TOK_SEMICOLON; + expr: TOK_IDENTIFIER | TOK_NUMBER | expr TOK_PLUS expr; + +.. figure:: ../images/basics_parsetree.* + :class: width-helper + :name: fig:Basics_parsetree + + Example parse tree for the Verilog expression + :verilog:`assign foo = bar + 42;` + +The parser converts the token list to the parse tree in :numref:`Fig. %s +<fig:Basics_parsetree>`. Note that the parse tree never actually exists as a +whole as data structure in memory. Instead the parser calls user-specified code +snippets (so-called reduce-functions) for all inner nodes of the parse tree in +depth-first order. + +In some very simple applications (e.g. code generation for stack machines) it is +possible to perform the task at hand directly in the reduce functions. But +usually the reduce functions are only used to build an in-memory data structure +with the relevant information from the parse tree. This data structure is called +an abstract syntax tree (AST). + +The exact format for the abstract syntax tree is application specific (while the +format of the parse tree and token list are mostly dictated by the grammar of +the language at hand). :numref:`Figure %s <fig:Basics_ast>` illustrates what an +AST for the parse tree in :numref:`Fig. %s <fig:Basics_parsetree>` could look +like. + +Usually the AST is then converted into yet another representation that is more +suitable for further processing. In compilers this is often an assembler-like +three-address-code intermediate representation. :cite:p:`Dragonbook` + +.. figure:: ../images/basics_ast.* + :class: width-helper + :name: fig:Basics_ast + + Example abstract syntax tree for the Verilog expression + :verilog:`assign foo = bar + 42;` + + +Multi-pass compilation +~~~~~~~~~~~~~~~~~~~~~~ + +Complex problems are often best solved when split up into smaller problems. This +is certainly true for compilers as well as for synthesis tools. The components +responsible for solving the smaller problems can be connected in two different +ways: through Single-Pass Pipelining and by using Multiple Passes. + +Traditionally a parser and lexer are connected using the pipelined approach: The +lexer provides a function that is called by the parser. This function reads data +from the input until a complete lexical token has been read. Then this token is +returned to the parser. So the lexer does not first generate a complete list of +lexical tokens and then pass it to the parser. Instead they run concurrently and +the parser can consume tokens as the lexer produces them. + +The single-pass pipelining approach has the advantage of lower memory footprint +(at no time must the complete design be kept in memory) but has the disadvantage +of tighter coupling between the interacting components. + +Therefore single-pass pipelining should only be used when the lower memory +footprint is required or the components are also conceptually tightly coupled. +The latter certainly is the case for a parser and its lexer. But when data is +passed between two conceptually loosely coupled components it is often +beneficial to use a multi-pass approach. + +In the multi-pass approach the first component processes all the data and the +result is stored in a in-memory data structure. Then the second component is +called with this data. This reduces complexity, as only one component is running +at a time. It also improves flexibility as components can be exchanged easier. + +Most modern compilers are multi-pass compilers. + +Static Single Assignment (SSA) form +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +In imperative programming (and behavioural HDL design) it is possible to assign +the same variable multiple times. This can either mean that the variable is +independently used in two different contexts or that the final value of the +variable depends on a condition. + +The following examples show C code in which one variable is used independently +in two different contexts: + +.. code:: c++ + :number-lines: + + void demo1() + { + int a = 1; + printf("%d\n", a); + + a = 2; + printf("%d\n", a); + } + +.. code:: c++ + + void demo1() + { + int a = 1; + printf("%d\n", a); + + int b = 2; + printf("%d\n", b); + } + +.. code:: c++ + :number-lines: + + void demo2(bool foo) + { + int a; + if (foo) { + a = 23; + printf("%d\n", a); + } else { + a = 42; + printf("%d\n", a); + } + } + +.. code:: c++ + + void demo2(bool foo) + { + int a, b; + if (foo) { + a = 23; + printf("%d\n", a); + } else { + b = 42; + printf("%d\n", b); + } + } + +In both examples the left version (only variable ``a``) and the right version +(variables ``a`` and ``b``) are equivalent. Therefore it is desired for further +processing to bring the code in an equivalent form for both cases. + +In the following example the variable is assigned twice but it cannot be easily +replaced by two variables: + +.. code:: c++ + + void demo3(bool foo) + { + int a = 23 + if (foo) + a = 42; + printf("%d\n", a); + } + +Static single assignment (SSA) form is a representation of imperative code that +uses identical representations for the left and right version of demos 1 and 2, +but can still represent demo 3. In SSA form each assignment assigns a new +variable (usually written with an index). But it also introduces a special +:math:`\Phi`-function to merge the different instances of a variable when +needed. In C-pseudo-code the demo 3 would be written as follows using SSA from: + +.. code:: c++ + + void demo3(bool foo) + { + int a_1, a_2, a_3; + a_1 = 23 + if (foo) + a_2 = 42; + a_3 = phi(a_1, a_2); + printf("%d\n", a_3); + } + +The :math:`\Phi`-function is usually interpreted as "these variables must be +stored in the same memory location" during code generation. Most modern +compilers for imperative languages such as C/C++ use SSA form for at least some +of its passes as it is very easy to manipulate and analyse. + +.. [1] + In recent years formal equivalence checking also became an important + verification method for validating RTL and lower abstraction + representation of the design. |