next up previous contents
Next: Loop handling Up: VHDL generation Previous: VHDL generation

Branch-compression

For code without loops, the conditional branches and gotos need to be translated into if-then-else statements, from which the VHDL compiler will create combinational logic. The trouble is that constructs such as the one shown in figure 4 do not have equivalent if-constructs. These control-flow patterns can be generated by source-language goto statements or short-circuit logical operators. The algorithm devised in this work combines dominator tree and flow-graph information to define a ``merge node,'' where the two control flows of the conditional will merge (if ever).[*] Statements must then be duplicated along each side of the conditional, until the merge node is reached, or all statements have been translated. Figure 5 shows the resultant VHDL for the quadruples in figure 4.


  
Figure 4: A flowgraph which can not be represented as an if-then-else statement without quadruple duplication.
\begin{figure}
\begin{center}
{\tt
\begin{tabular}
{ll}
 &if $a$\space then goto...
 ...space \\  &goto $L_4$\space \\ $L_4$:& \\ \end{tabular}}\end{center}\end{figure}


  
Figure 5: Conversion of the program of figure 4 to VHDL.
\begin{figure}
\begin{center}
{\tt\begin{tabular}
{l}
if a then \\ ~~if b then \...
 ...f; \\ else \\ ~~f := g + h; \\ end if; \\ \end{tabular}}\end{center}\end{figure}



C. Scott Ananian
10/11/1997