From 8f4dda3ded16f2604c070736cbde8849774755a8 Mon Sep 17 00:00:00 2001 From: Tristan Gingold Date: Mon, 10 Feb 2020 07:00:31 +0100 Subject: synth: rework (again) memory inference. Preliminary work to support multi-clock memories. Strengthen and fix fallout of Check_Connected. Rename synth.inference to netlists.inference. --- src/synth/netlists-cleanup.adb | 2 + src/synth/netlists-expands.adb | 4 +- src/synth/netlists-inference.adb | 694 +++++++++++++++++++++++++++++++++++++++ src/synth/netlists-inference.ads | 40 +++ src/synth/netlists-memories.adb | 275 +++++++++++++--- src/synth/netlists-memories.ads | 7 + src/synth/netlists.adb | 21 +- src/synth/synth-environment.adb | 32 +- src/synth/synth-inference.adb | 690 -------------------------------------- src/synth/synth-inference.ads | 37 --- 10 files changed, 1017 insertions(+), 785 deletions(-) create mode 100644 src/synth/netlists-inference.adb create mode 100644 src/synth/netlists-inference.ads delete mode 100644 src/synth/synth-inference.adb delete mode 100644 src/synth/synth-inference.ads (limited to 'src') diff --git a/src/synth/netlists-cleanup.adb b/src/synth/netlists-cleanup.adb index 4b4360e7f..bb963633a 100644 --- a/src/synth/netlists-cleanup.adb +++ b/src/synth/netlists-cleanup.adb @@ -133,6 +133,8 @@ package body Netlists.Cleanup is -- Only when the output is driven. Disconnect (Inp); Redirect_Inputs (Get_Output (Inst, 0), O); + else + Disconnect (Get_First_Sink (Get_Output (Inst, 0))); end if; Remove_Instance (Inst); end if; diff --git a/src/synth/netlists-expands.adb b/src/synth/netlists-expands.adb index 8794ad722..bab2b9b47 100644 --- a/src/synth/netlists-expands.adb +++ b/src/synth/netlists-expands.adb @@ -209,6 +209,7 @@ package body Netlists.Expands is end; -- 3. build mux tree + Disconnect (Get_Input (Inst, 1)); Extract_Address (Ctxt, Addr_Net, Ndims, Addr); Truncate_Address (Ctxt, Addr, Nbr_Els); Def := No_Net; @@ -216,7 +217,6 @@ package body Netlists.Expands is -- 4. remove old dyn_extract. Disconnect (Get_Input (Inst, 0)); - Disconnect (Get_Input (Inst, 1)); Redirect_Inputs (Get_Output (Inst, 0), Res); Remove_Instance (Inst); @@ -396,6 +396,7 @@ package body Netlists.Expands is -- Generate decoder. Net_Arr := new Net_Array(0 .. Int32 (Nbr_Els - 1)); + Disconnect (Get_Input (Inst, 2)); Extract_Address (Ctxt, Addr_Net, Ndims, Addr); Truncate_Address (Ctxt, Addr, Nbr_Els); Generate_Decoder (Ctxt, Addr, Net_Arr.all); @@ -419,7 +420,6 @@ package body Netlists.Expands is Redirect_Inputs (O, Res); Disconnect (Get_Input (Inst, 0)); Disconnect (Get_Input (Inst, 1)); - Disconnect (Get_Input (Inst, 2)); if En /= No_Net then Disconnect (Get_Input (Inst, 3)); end if; diff --git a/src/synth/netlists-inference.adb b/src/synth/netlists-inference.adb new file mode 100644 index 000000000..3bd1a8f77 --- /dev/null +++ b/src/synth/netlists-inference.adb @@ -0,0 +1,694 @@ +-- Inference in synthesis. +-- Copyright (C) 2017 Tristan Gingold +-- +-- This file is part of GHDL. +-- +-- This program is free software; you can redistribute it and/or modify +-- it under the terms of the GNU General Public License as published by +-- the Free Software Foundation; either version 2 of the License, or +-- (at your option) any later version. +-- +-- This program is distributed in the hope that it will be useful, +-- but WITHOUT ANY WARRANTY; without even the implied warranty of +-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +-- GNU General Public License for more details. +-- +-- You should have received a copy of the GNU General Public License +-- along with this program; if not, write to the Free Software +-- Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, +-- MA 02110-1301, USA. + +with Netlists.Utils; use Netlists.Utils; +with Netlists.Gates; use Netlists.Gates; +with Netlists.Gates_Ports; use Netlists.Gates_Ports; +with Netlists.Locations; use Netlists.Locations; +with Netlists.Errors; use Netlists.Errors; +with Netlists.Internings; +with Netlists.Folds; use Netlists.Folds; +with Netlists.Memories; + +with Synth.Flags; +with Synth.Source; use Synth.Source; +with Synth.Errors; use Synth.Errors; + +package body Netlists.Inference is + -- DFF inference. + -- As an initial implementation, the following 'styles' must be + -- supported: + -- Note: rising_edge is any clock_edge; '<=' can be ':='. + -- + -- 1) + -- if rising_edge(clk) then + -- r <= x; + -- end if; + -- + -- 2) + -- if rst = '0' then + -- r <= x; + -- elsif rising_edge (clk) then + -- r <= y; + -- end if; + -- + -- 3) + -- wait until rising_edge(clk); + -- r <= x; + -- Which is equivalent to 1) when the wait statement is the only and first + -- statement, as it can be converted to an if statement. + -- + -- Netlist derived from 1) + -- +------+ + -- | | + -- | /| | + -- | |0+-+ + -- Q --+--+ | + -- |1+--- D + -- \| + -- CLK + -- This is a memorizing element as there is a loop, the value is changed + -- to D on a rising edge of the clock. + -- + -- Netlist derived from 2) + -- +------------+ + -- | /| | + -- | /| |0+-+ + -- | |0+---+ | + -- Q --+--+ | |1+----- D + -- |1+-+ \| + -- \| | CLK + -- RST +--------- '0' + -- This is a memorizing element as there is a loop. It is an asynchronous + -- reset as Q is forced to '0' when RST is asserted. + + function Has_Clock (N : Net) return Boolean + is + Inst : constant Instance := Get_Net_Parent (N); + begin + case Get_Id (Inst) is + when Id_Edge => + return True; + when Id_And => + -- Assume the condition is canonicalized, ie of the form: + -- CLK and EXPR. + -- FIXME: do it! + return Has_Clock (Get_Input_Net (Inst, 0)); + when others => + return False; + end case; + end Has_Clock; + + -- Find the longest chain of mux starting from VAL with a final input + -- of PREV_VAL. Such a chain means this is a memorising element. + -- RES is the last mux in the chain, DIST the number of mux in the chain. + procedure Find_Longest_Loop + (Val : Net; Prev_Val : Net; Res : out Instance; Dist : out Integer) + is + Inst : constant Instance := Get_Net_Parent (Val); + begin + if Get_Id (Inst) = Id_Mux2 then + declare + Res0, Res1 : Instance; + Dist0, Dist1 : Integer; + begin + if Has_Clock (Get_Driver (Get_Mux2_Sel (Inst))) then + Res := Inst; + Dist := 1; + else + Find_Longest_Loop + (Get_Driver (Get_Mux2_I0 (Inst)), Prev_Val, Res0, Dist0); + Find_Longest_Loop + (Get_Driver (Get_Mux2_I1 (Inst)), Prev_Val, Res1, Dist1); + -- Input1 has an higher priority than input0 in case + -- the selector is a clock. + -- FIXME: improve algorithm. + if Dist1 > Dist0 then + Dist := Dist1 + 1; + if Dist1 > 0 then + Res := Res1; + else + Res := Inst; + end if; + elsif Dist0 >= 0 then + Dist := Dist0 + 1; + if Dist0 > 0 then + Res := Res0; + else + Res := Inst; + end if; + else + pragma Assert (Dist1 < 0 and Dist0 < 0); + Res := No_Instance; + Dist := -1; + end if; + end if; + end; + elsif Val = Prev_Val then + Res := No_Instance; + Dist := 0; + else + Res := No_Instance; + Dist := -1; + end if; + end Find_Longest_Loop; + + procedure Extract_Clock_And (Ctxt : Context_Acc; Inst : Instance) + is + begin + pragma Assert (Get_Id (Inst) = Id_And); + + declare + I0 : constant Input := Get_Input (Inst, 0); + N0 : constant Net := Get_Driver (I0); + Inst0 : constant Instance := Get_Net_Parent (N0); + begin + case Get_Id (Inst0) is + when Id_Edge => + null; + when Id_And => + Extract_Clock_And (Ctxt, Inst0); + + -- If we have: AND convert to: AND + -- / \ / \ + -- N1 AND0 ==> AND0 EDGE + -- / \ / \ + -- N2 EDGE N1 N2 + declare + I3 : constant Input := Get_Input (Inst0, 0); + N3 : constant Net := Get_Driver (I3); + Inst3 : constant Instance := Get_Net_Parent (N3); + begin + if Get_Id (Inst3) = Id_Edge then + declare + Can_Rotate : constant Boolean := + Has_One_Connection (N0); + I2 : constant Input := Get_Input (Inst0, 1); + N2 : constant Net := Get_Driver (I2); + I1 : constant Input := Get_Input (Inst, 1); + N1 : constant Net := Get_Driver (I1); + N4 : Net; + begin + Disconnect (I0); + Disconnect (I1); + Connect (I0, N3); + if Can_Rotate then + Disconnect (I2); + Disconnect (I3); + + Connect (I1, N0); + Connect (I3, N2); + Connect (I2, N1); + else + N4 := Build_Dyadic (Ctxt, Id_And, N2, N1); + Connect (I1, N4); + end if; + end; + end if; + end; + when others => + null; + end case; + end; + + declare + I0 : constant Input := Get_Input (Inst, 1); + N0 : constant Net := Get_Driver (I0); + Inst0 : constant Instance := Get_Net_Parent (N0); + begin + case Get_Id (Inst0) is + when Id_Edge => + -- Swap inputs 0 and 1. + declare + I1 : constant Input := Get_Input (Inst, 0); + N1 : constant Net := Get_Driver (I1); + begin + Disconnect (I0); + Disconnect (I1); + Connect (I1, N0); + Connect (I0, N1); + end; + when Id_And => + Extract_Clock_And (Ctxt, Inst0); + + -- If we have: AND convert to: AND + -- / \ / \ + -- AND0 N1 ==> AND0 EDGE + -- / \ / \ + -- N2 EDGE N2 N1 + declare + I3 : constant Input := Get_Input (Inst0, 0); + N3 : constant Net := Get_Driver (I3); + begin + if Get_Id (Get_Net_Parent (N3)) = Id_Edge then + declare + Can_Rotate : constant Boolean := + Has_One_Connection (N0); + I1 : constant Input := Get_Input (Inst, 0); + N1 : constant Net := Get_Driver (I1); + N4 : Net; + begin + Disconnect (I3); + Disconnect (I1); + Connect (I1, N3); + if Can_Rotate then + Connect (I3, N1); + else + N4 := Build_Dyadic + (Ctxt, Id_And, N1, Get_Input_Net (Inst0, 1)); + Connect (I3, N4); + end if; + end; + end if; + end; + when others => + null; + end case; + end; + end Extract_Clock_And; + + -- Walk the And-net N, and extract clock (posedge/negedge) if found. + -- ENABLE is N without the clock. + -- If not found, CLK and ENABLE are set to No_Net. + procedure Extract_Clock + (Ctxt : Context_Acc; N : Net; Clk : out Net; Enable : out Net) + is + Inst : constant Instance := Get_Net_Parent (N); + begin + Clk := No_Net; + Enable := No_Net; + + case Get_Id (Inst) is + when Id_Edge => + -- Get rid of the edge gate, just return the signal. + Clk := Get_Input_Net (Inst, 0); + when Id_And => + -- Canonicalize conditions. + Extract_Clock_And (Ctxt, Inst); + + -- Condition should be in the form: CLK and EXPR + declare + I0 : constant Net := Get_Input_Net (Inst, 0); + Inst0 : constant Instance := Get_Net_Parent (I0); + begin + if Get_Id (Inst0) = Id_Edge then + -- INST is clearly not synthesizable (boolean operation on + -- an edge). Will be removed at the end by + -- remove_unused_instances. Do not remove it now as its + -- output may be used by other nets. + Clk := Get_Input_Net (Inst0, 0); + Enable := Get_Input_Net (Inst, 1); + return; + end if; + end; + when others => + null; + end case; + end Extract_Clock; + + function Is_Prev_FF_Value (V : Net; Prev_Val : Net; Off : Uns32) + return Boolean + is + Inst : Instance; + begin + if V = Prev_Val then + pragma Assert (Off = 0); + return True; + end if; + Inst := Get_Net_Parent (V); + return Get_Id (Inst) = Id_Extract + and then Get_Param_Uns32 (Inst, 0) = Off + and then Get_Input_Net (Inst, 0) = Prev_Val; + end Is_Prev_FF_Value; + + -- LAST_MUX is the mux whose input 0 is the loop and clock for selector. + function Infere_FF (Ctxt : Context_Acc; + Prev_Val : Net; + Off : Uns32; + Last_Mux : Instance; + Clk : Net; + Clk_Enable : Net; + Stmt : Synth.Source.Syn_Src) return Net + is + O : constant Net := Get_Output (Last_Mux, 0); + Data : Net; + Res : Net; + Sig : Instance; + Init : Net; + Rst : Net; + Rst_Val : Net; + Enable : Net; + begin + -- Create and return the DFF. + + -- 1. Remove the mux that creates the loop (will be replaced by the + -- dff). + declare + Sel : constant Input := Get_Mux2_Sel (Last_Mux); + I0 : constant Input := Get_Mux2_I0 (Last_Mux); + I1 : constant Input := Get_Mux2_I1 (Last_Mux); + begin + -- There must be no 'else' part for clock expression. + if not Is_Prev_FF_Value (Get_Driver (I0), Prev_Val, Off) then + Error_Msg_Synth + (+Stmt, "synchronous code does not expect else part"); + return Prev_Val; + end if; + + Disconnect (Sel); + -- Don't try to free driver of I0 as this is Prev_Val or a selection + -- of it. + Disconnect (I0); + Data := Get_Driver (I1); + -- Don't try to free driver of I1 as it is reconnected. + Disconnect (I1); + end; + + -- If the signal declaration has an initial value, get it. + Sig := Get_Net_Parent (Prev_Val); + if Get_Id (Get_Module (Sig)) = Id_Isignal then + Init := Get_Input_Net (Sig, 1); + Init := Build2_Extract (Ctxt, Init, Off, Get_Width (O)); + else + Init := No_Net; + end if; + + Enable := Clk_Enable; + + -- Look for asynchronous set/reset. They are muxes after the loop + -- mux. In theory, there can be many set/reset with a defined order. + Rst_Val := No_Net; + Rst := No_Net; + declare + Done : Boolean; + Mux : Instance; + Sel : Net; + Last_Out : Net; + Mux_Not_Rst : Net; + Mux_Rst : Net; + Mux_Rst_Val : Net; + begin + Last_Out := O; + + -- Initially, the final output is not connected. So walk from the + -- clocked mux until reaching the final output. + Done := not Is_Connected (Last_Out); + + while not Done loop + if not Has_One_Connection (Last_Out) + and then not Is_Const_Net (Last_Out) + then + -- TODO. + raise Internal_Error; + end if; + + -- The parent must be a mux (it's a chain of muxes). + Mux := Get_Input_Parent (Get_First_Sink (Last_Out)); + pragma Assert (Get_Id (Mux) = Id_Mux2); + + -- Extract the reset condition and the reset value. + Sel := Get_Driver (Get_Mux2_Sel (Mux)); + if Get_Driver (Get_Mux2_I0 (Mux)) = Last_Out then + Mux_Rst_Val := Get_Driver (Get_Mux2_I1 (Mux)); + Mux_Rst := Sel; + elsif Get_Driver (Get_Mux2_I1 (Mux)) = Last_Out then + Mux_Rst_Val := Get_Driver (Get_Mux2_I0 (Mux)); + Mux_Rst := Build_Monadic (Ctxt, Id_Not, Sel); + else + -- Cannot happen. + raise Internal_Error; + end if; + + Last_Out := Get_Output (Mux, 0); + Done := not Is_Connected (Last_Out); + + if Is_Prev_FF_Value (Mux_Rst_Val, Prev_Val, Off) then + -- The mux is like an enable. Like in this example, q2 is not + -- assigned when RST is true: + -- if rst then + -- q1 <= '0'; + -- elsif rising_edge(clk) then + -- q2 <= d2; + -- q1 <= d1; + -- end if; + + -- Remove the mux + Disconnect (Get_Mux2_I0 (Mux)); + Disconnect (Get_Mux2_I1 (Mux)); + Disconnect (Get_Mux2_Sel (Mux)); + + -- Add the negation of the condition to the enable signal. + -- Negate the condition for the current reset. + Mux_Not_Rst := Build_Monadic (Ctxt, Id_Not, Mux_Rst); + if Rst /= No_Net then + Rst := Build_Dyadic (Ctxt, Id_And, Rst, Mux_Not_Rst); + end if; + if Enable = No_Net then + Enable := Mux_Not_Rst; + else + Enable := Build_Dyadic (Ctxt, Id_And, Enable, Mux_Not_Rst); + end if; + else + -- Assume this is a reset value. + -- FIXME: check for no logical loop. + + if Rst = No_Net then + -- Remove the last mux. Dedicated inputs on the FF + -- are used. + Disconnect (Get_Mux2_I0 (Mux)); + Disconnect (Get_Mux2_I1 (Mux)); + Disconnect (Get_Mux2_Sel (Mux)); + + -- The output of the mux is now the reset value. + Redirect_Inputs (Last_Out, Mux_Rst_Val); + Free_Instance (Mux); + + Rst := Mux_Rst; + Rst_Val := Mux_Rst_Val; + Last_Out := Mux_Rst_Val; + else + Rst := Build_Dyadic (Ctxt, Id_Or, Mux_Rst, Rst); + Rst_Val := Last_Out; + end if; + end if; + end loop; + end; + + -- If there is a condition with the clock, that's an enable which + -- keep the previous value if the condition is false. Add the mux + -- for it. + if Enable /= No_Net then + declare + Prev : Net; + begin + Prev := Build2_Extract (Ctxt, Prev_Val, Off, Get_Width (Data)); + + Data := Build_Mux2 (Ctxt, Enable, Prev, Data); + Copy_Location (Data, Enable); + end; + end if; + + -- Create the FF. + if Rst = No_Net then + pragma Assert (Rst_Val = No_Net); + if Init /= No_Net then + Res := Build_Idff (Ctxt, Clk, D => Data, Init => Init); + else + Res := Build_Dff (Ctxt, Clk, D => Data); + end if; + else + if Init /= No_Net then + Res := Build_Iadff (Ctxt, Clk, D => Data, + Rst => Rst, Rst_Val => Rst_Val, + Init => Init); + else + Res := Build_Adff (Ctxt, Clk, D => Data, + Rst => Rst, Rst_Val => Rst_Val); + end if; + end if; + Copy_Location (Res, Last_Mux); + + -- The output of the mux may be read later in the process, + -- like this: + -- if clk'event and clk = '1' then + -- d := i + 1; + -- end if; + -- d1 := d + 1; + -- So connections to the mux output are redirected to dff + -- output. + Redirect_Inputs (O, Res); + + Free_Instance (Last_Mux); + + return Res; + end Infere_FF; + + -- Detect false combinational loop. They can easily appear when variables + -- are only used in one branch: + -- process (all) + -- variable a : std_logic; + -- begin + -- r <= '1'; + -- if sel = '1' then + -- a := '1'; + -- r <= '0'; + -- end if; + -- end process; + -- There is a combinational path from 'a' to 'a' as + -- a := (sel = '1') ? '1' : a; + -- But this is a false loop because the value of 'a' is never used. In + -- that case, 'a' is assigned to 'x' and all the unused logic will be + -- removed during clean-up. + -- + -- Detection is very simple: the closure of readers of 'a' must be only + -- muxes (which were inserted by controls). + function Is_False_Loop (Prev_Val : Net) return Boolean + is + package Inst_Interning renames + Netlists.Internings.Dyn_Instance_Interning; + use Inst_Interning; + T : Inst_Interning.Instance; + + function Add_From_Net (N : Net) return Boolean + is + Inst : Netlists.Instance; + Inp : Input; + begin + Inp := Get_First_Sink (N); + while Inp /= No_Input loop + Inst := Get_Input_Parent (Inp); + if Get_Id (Inst) not in Mux_Module_Id then + return False; + end if; + + -- Add to T (if not already). + Get (T, Inst, Inst); + + Inp := Get_Next_Sink (Inp); + end loop; + + return True; + end Add_From_Net; + + function Walk_Nets (N : Net) return Boolean + is + Inst : Netlists.Instance; + begin + -- Put gates that read the value. + if not Add_From_Net (N) then + return False; + end if; + + -- Follow the outputs. + for I in First_Index .. Index_Type'Last loop + exit when I > Inst_Interning.Last_Index (T); + Inst := Get_By_Index (T, I); + if not Add_From_Net (Get_Output (Inst, 0)) then + return False; + end if; + end loop; + + -- No external readers. + return True; + end Walk_Nets; + + Res : Boolean; + begin + Inst_Interning.Init (T); + + Res := Walk_Nets (Prev_Val); + + Inst_Interning.Free (T); + + return Res; + end Is_False_Loop; + + function Infere_Latch (Ctxt : Context_Acc; + Val : Net; + Prev_Val : Net; + Stmt : Synth.Source.Syn_Src) return Net + is + Name : Sname; + begin + -- In case of false loop, do not close the loop but assign X. + if Is_False_Loop (Prev_Val) then + return Build_Const_X (Ctxt, Get_Width (Val)); + end if; + + -- Latch or combinational loop. + if Get_Id (Get_Net_Parent (Prev_Val)) = Id_Output then + -- Outputs are connected to a port. The port is the first connection + -- made, so it is the last sink. Be more tolerant and look for + -- the (only) port connected to the output. + declare + Inp : Input; + Inst : Instance; + begin + Inp := Get_First_Sink (Prev_Val); + loop + pragma Assert (Inp /= No_Input); + Inst := Get_Input_Parent (Inp); + if Get_Id (Inst) >= Id_User_None then + Name := Get_Output_Desc (Get_Module (Inst), + Get_Port_Idx (Inp)).Name; + exit; + end if; + Inp := Get_Next_Sink (Inp); + end loop; + end; + else + Name := Get_Instance_Name (Get_Net_Parent (Prev_Val)); + end if; + Error_Msg_Synth (+Stmt, "latch infered for net %n", +Name); + + return Val; + end Infere_Latch; + + -- Note: PREV_VAL is the wire gate, so with full width and no offset. + function Infere (Ctxt : Context_Acc; + Val : Net; + Off : Uns32; + Prev_Val : Net; + Stmt : Synth.Source.Syn_Src) return Net + is + use Netlists.Memories; + pragma Assert (Val /= No_Net); + pragma Assert (Prev_Val /= No_Net); + Last_Mux : Instance; + Len : Integer; + Sel : Input; + Clk : Net; + Enable : Net; + Res : Net; + begin + if not Synth.Flags.Flag_Debug_Noinference then + if Get_First_Sink (Prev_Val) = No_Input then + -- PREV_VAL is never read, so there cannot be any loop. + -- This is an important optimization for control signals. + Len := -1; + else + Find_Longest_Loop (Val, Prev_Val, Last_Mux, Len); + end if; + else + Len := -1; + end if; + if Len <= 0 then + -- No logical loop or self assignment. + Res := Val; + elsif Can_Infere_RAM (Val, Prev_Val) then + -- Try to infere RAM before FF, because of many ports/clocks. + Res := Infere_RAM (Ctxt, Val); + else + -- So there is a logical loop. + Sel := Get_Mux2_Sel (Last_Mux); + Extract_Clock (Ctxt, Get_Driver (Sel), Clk, Enable); + if Clk = No_Net then + -- No clock -> latch or combinational loop + Res := Infere_Latch (Ctxt, Val, Prev_Val, Stmt); + else + -- Clock -> FF + Res := Infere_FF (Ctxt, Prev_Val, Off, Last_Mux, + Clk, Enable, Stmt); + end if; + end if; + + return Res; + end Infere; +end Netlists.Inference; diff --git a/src/synth/netlists-inference.ads b/src/synth/netlists-inference.ads new file mode 100644 index 000000000..b034ec301 --- /dev/null +++ b/src/synth/netlists-inference.ads @@ -0,0 +1,40 @@ +-- Inference in synthesis. +-- Copyright (C) 2017 Tristan Gingold +-- +-- This file is part of GHDL. +-- +-- This program is free software; you can redistribute it and/or modify +-- it under the terms of the GNU General Public License as published by +-- the Free Software Foundation; either version 2 of the License, or +-- (at your option) any later version. +-- +-- This program is distributed in the hope that it will be useful, +-- but WITHOUT ANY WARRANTY; without even the implied warranty of +-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +-- GNU General Public License for more details. +-- +-- You should have received a copy of the GNU General Public License +-- along with this program; if not, write to the Free Software +-- Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, +-- MA 02110-1301, USA. + +with Netlists; use Netlists; +with Netlists.Builders; use Netlists.Builders; +with Synth.Source; + +package Netlists.Inference is + -- Walk the And-net N, and extract clock (posedge/negedge) if found. + -- ENABLE is N without the clock. + -- If not found, CLK and ENABLE are set to No_Net. + procedure Extract_Clock + (Ctxt : Context_Acc; N : Net; Clk : out Net; Enable : out Net); + + -- To be called when there is an assignment to a signal/output of VAL and + -- the previous value is PREV_VAL (an Id_Signal or Id_Output). + -- If there is a loop, infere a dff or a latch or emit an error. + function Infere (Ctxt : Context_Acc; + Val : Net; + Off : Uns32; + Prev_Val : Net; + Stmt : Synth.Source.Syn_Src) return Net; +end Netlists.Inference; diff --git a/src/synth/netlists-memories.adb b/src/synth/netlists-memories.adb index d5013066a..7037f67cd 100644 --- a/src/synth/netlists-memories.adb +++ b/src/synth/netlists-memories.adb @@ -29,6 +29,7 @@ with Netlists.Locations; use Netlists.Locations; with Netlists.Errors; use Netlists.Errors; with Netlists.Concats; with Netlists.Folds; use Netlists.Folds; +with Netlists.Inference; with Synth.Errors; use Synth.Errors; @@ -1029,6 +1030,44 @@ package body Netlists.Memories is end case; end Validate_RAM; + function Validate_RAM_Simple (Sig : Instance) return Boolean + is + Inst : Instance; + N : Net; + Inp : Input; + Ok : Boolean; + begin + Ok := False; + N := Get_Output (Sig, 0); + while N /= No_Net loop + Inp := Get_First_Sink (N); + N := No_Net; + + while Inp /= No_Input loop + Inst := Get_Input_Parent (Inp); + case Get_Id (Inst) is + when Id_Dyn_Insert_En => + if N /= No_Net then + return False; + end if; + N := Get_Output (Inst, 0); + when Id_Dyn_Extract => + null; + when Id_Isignal + | Id_Signal => + if Inst /= Sig then + return False; + end if; + Ok := True; + when others => + return False; + end case; + Inp := Get_Next_Sink (Inp); + end loop; + end loop; + return Ok; + end Validate_RAM_Simple; + function Add_Enable_To_Dyn_Insert (Ctxt : Context_Acc; Inst : Instance; Sel : Net) return Instance is @@ -1037,7 +1076,6 @@ package body Netlists.Memories is In_Idx : constant Input := Get_Input (Inst, 2); Off : constant Uns32 := Get_Param_Uns32 (Inst, 0); Dest : constant Input := Get_First_Sink (Get_Output (Inst, 0)); - pragma Assert (Has_One_Connection (Get_Output (Inst, 0))); Res : Net; begin Res := Build_Dyn_Insert_En @@ -1048,8 +1086,12 @@ package body Netlists.Memories is Disconnect (In_Mem); Disconnect (In_V); Disconnect (In_Idx); - Disconnect (Dest); - Connect (Dest, Res); + if Dest /= No_Input then + -- Only one connection. + pragma Assert (Get_Next_Sink (Dest) = No_Input); + Disconnect (Dest); + Connect (Dest, Res); + end if; Remove_Instance (Inst); @@ -1058,10 +1100,13 @@ package body Netlists.Memories is -- Remove the mux2 MUX (by adding enable to dyn_insert). -- Return the new head. - function Reduce_Muxes_Mux2 (Ctxt : Context_Acc; Mux : Instance) - return Instance + procedure Reduce_Muxes_Mux2 (Ctxt : Context_Acc; + Psel : Net; + Head : in out Instance; + Tail : out Instance) is - Dest : constant Input := Get_First_Sink (Get_Output (Mux, 0)); + Mux : constant Instance := Head; + Muxout : constant Net := Get_Output (Mux, 0); Sel_Inp : constant Input := Get_Input (Mux, 0); In0 : constant Input := Get_Input (Mux, 1); In1 : constant Input := Get_Input (Mux, 2); @@ -1103,8 +1148,6 @@ package body Netlists.Memories is Disconnect (In0); Disconnect (In1); Disconnect (Sel_Inp); - Disconnect (Dest); - Connect (Dest, Drv0); Drv := Drv0; Src := Drv1; Sel := Build_Monadic (Ctxt, Id_Not, Sel); @@ -1113,8 +1156,6 @@ package body Netlists.Memories is Disconnect (In0); Disconnect (In1); Disconnect (Sel_Inp); - Disconnect (Dest); - Connect (Dest, Drv1); Drv := Drv1; Src := Drv0; else @@ -1122,7 +1163,9 @@ package body Netlists.Memories is raise Internal_Error; end if; - Remove_Instance (Mux); + if Psel /= No_Net then + Sel := Build_Dyadic (Ctxt, Id_And, Psel, Sel); + end if; -- Reduce Drv until Src. -- Transform dyn_insert to dyn_insert_en by adding SEL, or simply add @@ -1134,18 +1177,21 @@ package body Netlists.Memories is case Get_Id (Inst) is when Id_Mux2 => -- Recurse on the mux. - Inst := Reduce_Muxes_Mux2 (Ctxt, Inst); - -- But continue with the result: still need to add the SEL. - Drv := Get_Output (Inst, 0); + Reduce_Muxes_Mux2 (Ctxt, Sel, Inst, Tail); + if Res = No_Instance then + Res := Inst; + end if; + -- Continue the walk with the next element. + Drv := Get_Input_Net (Inst, 0); when Id_Dyn_Insert => -- Transform dyn_insert to dyn_insert_en. - Inst := Add_Enable_To_Dyn_Insert (Ctxt, Inst, Sel); + Tail := Add_Enable_To_Dyn_Insert (Ctxt, Inst, Sel); -- If this is the head, keep it. if Res = No_Instance then - Res := Inst; + Res := Tail; end if; -- Continue the walk with the next element. - Drv := Get_Input_Net (Inst, 0); + Drv := Get_Input_Net (Tail, 0); when Id_Dyn_Insert_En => -- Simply add SEL to the enable input. declare @@ -1162,23 +1208,31 @@ package body Netlists.Memories is Res := Inst; end if; -- Continue the walk with the next element. + Tail := Inst; Drv := Get_Input_Net (Inst, 0); when others => raise Internal_Error; end case; end loop; - return Res; + Redirect_Inputs (Muxout, Get_Output (Res, 0)); + Remove_Instance (Mux); + + Head := Res; end Reduce_Muxes_Mux2; -- From SIG (the signal/isignal for the RAM), move all the muxes to the -- dyn_insert. The dyn_insert may be transformed to dyn_insert_en. -- At the end, the loop is linear and without muxes. - procedure Reduce_Muxes (Ctxt : Context_Acc; Sig : Instance) + -- Return the new head. + function Reduce_Muxes (Ctxt : Context_Acc; Sig : Instance) return Instance is + pragma Assert (not Is_Connected (Get_Output (Sig, 0))); Inst : Instance; + Tail : Instance; + Res : Instance; begin - Inst := Get_Input_Instance (Sig, 0); + Inst := Sig; -- Skip dff/idff. -- FIXME: that should be considered as an implicit mux. @@ -1186,9 +1240,10 @@ package body Netlists.Memories is case Get_Id (Inst) is when Id_Dff | Id_Idff => + Res := Inst; Inst := Get_Input_Instance (Inst, 1); when others => - null; + Res := No_Instance; end case; -- Walk until the reaching SIG again. @@ -1196,18 +1251,22 @@ package body Netlists.Memories is case Get_Id (Inst) is when Id_Mux2 => -- Reduce the mux. - Inst := Reduce_Muxes_Mux2 (Ctxt, Inst); + Reduce_Muxes_Mux2 (Ctxt, No_Net, Inst, Tail); + if Res = No_Instance then + Res := Inst; + end if; + Inst := Tail; when Id_Dyn_Insert | Id_Dyn_Insert_En => + if Res = No_Instance then + Res := Inst; + end if; -- Skip the dyn_insert. Inst := Get_Input_Instance (Inst, 0); when Id_Signal | Id_Isignal => -- Should be done. - if Inst /= Sig then - raise Internal_Error; - end if; - return; + return Res; when others => raise Internal_Error; end case; @@ -1601,6 +1660,7 @@ package body Netlists.Memories is N_Inst : Instance; In_Inst : Instance; Dff_Clk : Net; + Prev_Inst : Instance; begin -- Try to extract clock from dff. Dff_Clk := No_Net; @@ -1613,10 +1673,13 @@ package body Netlists.Memories is null; end case; + Prev_Inst := No_Instance; + -- Do the real work: transform gates to ports. Inst := Sig; loop -- Check gates connected to the output. + -- First the dyn_extract N_Inst := No_Instance; Inp := Get_First_Sink (Get_Output (Inst, 0)); while Inp /= No_Input loop @@ -1677,10 +1740,10 @@ package body Netlists.Memories is end; when Id_Dyn_Insert_En | Id_Dyn_Insert - | Id_Dff - | Id_Idff | Id_Signal | Id_Isignal => + Inp := Get_Input (In_Inst, 0); + Disconnect (Inp); pragma Assert (N_Inst = No_Instance); N_Inst := In_Inst; when others => @@ -1689,6 +1752,10 @@ package body Netlists.Memories is Inp := N_Inp; end loop; + if Prev_Inst /= No_Instance then + Remove_Instance (Prev_Inst); + end if; + -- Handle INST. case Get_Id (Inst) is when Id_Dyn_Insert_En @@ -1704,31 +1771,35 @@ package body Netlists.Memories is Inp2 : Input; Dat : Net; En : Net; + Clk : Net; begin Off_Array_To_Idx (Offs.all, Off, Wd, Idx, Len); Inp2 := Get_Input (Inst, 2); Addr := Get_Driver (Inp2); Disconnect (Inp2); Convert_Memidx (Ctxt, Mem_Sz, Addr, Mem_W); - pragma Assert (Dff_Clk /= No_Net); if Get_Id (Inst) = Id_Dyn_Insert_En then Inp2 := Get_Input (Inst, 3); En := Get_Driver (Inp2); Disconnect (Inp2); + Inference.Extract_Clock (Ctxt, En, Clk, En); else + Clk := Dff_Clk; + En := No_Net; + end if; + pragma Assert (Clk /= No_Net); + if En = No_Net then En := Build_Const_UB32 (Ctxt, 1, 1); end if; for I in Idx .. Idx + Len - 1 loop Inp2 := Get_Input (Inst, 1); Dat := Get_Driver (Inp2); Wr_Inst := Build_Mem_Wr_Sync - (Ctxt, Tails (I), Addr, Dff_Clk, En, Dat); + (Ctxt, Tails (I), Addr, Clk, En, Dat); Disconnect (Inp2); Tails (I) := Get_Output (Wr_Inst, 0); end loop; end; - Inp := Get_Input (Inst, 0); - Disconnect (Inp); Remove_Instance (Inst); when Id_Dff | Id_Idff => @@ -1737,10 +1808,10 @@ package body Netlists.Memories is if Get_Id (Inst) = Id_Idff then Disconnect (Get_Input (Inst, 2)); end if; - Remove_Instance (Inst); + Prev_Inst := Inst; when Id_Signal | Id_Isignal => - null; + Prev_Inst := No_Instance; when others => raise Internal_Error; end case; @@ -1757,8 +1828,9 @@ package body Netlists.Memories is end case; end loop; + pragma Assert (Prev_Inst = No_Instance); + -- Finish to remove the signal/isignal. - Disconnect (Get_Input (Inst, 0)); Remove_Instance (Inst); end; @@ -1796,7 +1868,7 @@ package body Netlists.Memories is while Inst /= No_Instance loop -- Walk all the instances of M: case Get_Id (Inst) is - when Id_Dyn_Insert + when Id_Dyn_Insert_En | Id_Dyn_Extract => Instance_Tables.Append (Dyns, Inst); pragma Assert (Get_Mark_Flag (Inst) = False); @@ -1869,8 +1941,7 @@ package body Netlists.Memories is Replace_ROM_Memory (Ctxt, Inst); end if; else - if Validate_RAM (Inst) then - Reduce_Muxes (Ctxt, Inst); + if Validate_RAM_Simple (Inst) then Convert_To_Memory (Ctxt, Inst); end if; end if; @@ -1879,4 +1950,132 @@ package body Netlists.Memories is Instance_Tables.Free (Mems); end Extract_Memories2; + + function One_Write_Connection (O : Net) return Boolean + is + Inp : Input; + Nbr : Natural; + begin + Inp := Get_First_Sink (O); + Nbr := 0; + while Inp /= No_Input loop + if Get_Id (Get_Input_Parent (Inp)) /= Id_Dyn_Extract then + Nbr := Nbr + 1; + if Nbr > 1 then + return False; + end if; + end if; + Inp := Get_Next_Sink (Inp); + end loop; + return Nbr = 1; + end One_Write_Connection; + + function Can_Infere_RAM_Mux2 (Mux : Instance) return Instance + is + Drv0 : Net; + Drv1 : Net; + Drv : Net; + Src : Net; + Inst : Instance; + begin + -- An enable mux has this shape: + -- _ + -- / |----- dyn_insert ----+----+ + -- out --| | | +---- inp + -- \_|---------------------/ + -- + -- The dyn_insert can be on one input or the other of the mux. + -- The important point is that the output of the dyn_insert is connected + -- only to the mux, while the other mux input is connected to two nodes. + -- + -- There can be several dyn_inserts in a raw, like this: + -- _ + -- / |-- dyn_insert --- dyn_insert ---+----+ + -- out --| | | +---- inp + -- \_|--------------------------------/ + -- + -- Or even nested muxes: + -- _ + -- _ / |----- dyn_insert ----+----+ + -- / |--| | | | + -- out --| | \_|---------------------/ | + -- \_|--------------------------------+----- inp + Drv0 := Get_Input_Net (Mux, 1); + Drv1 := Get_Input_Net (Mux, 2); + if One_Write_Connection (Drv0) + and then not One_Write_Connection (Drv1) + then + Drv := Drv0; + Src := Drv1; + elsif One_Write_Connection (Drv1) + and then not One_Write_Connection (Drv0) + then + Drv := Drv1; + Src := Drv0; + else + -- Not an enable mux. + return No_Instance; + end if; + + -- Walk Drv until Src. + while Drv /= Src loop + Inst := Get_Net_Parent (Drv); + case Get_Id (Inst) is + when Id_Mux2 => + -- Recurse on the mux. + Inst := Can_Infere_RAM_Mux2 (Inst); + if Inst = No_Instance then + return No_Instance; + end if; + -- But continue with the result: still need to add the SEL. + Drv := Get_Output (Inst, 0); + when Id_Dyn_Insert => + -- Continue the walk with the next element. + Drv := Get_Input_Net (Inst, 0); + when others => + return No_Instance; + end case; + end loop; + + return Get_Net_Parent (Src); + end Can_Infere_RAM_Mux2; + + function Can_Infere_RAM (Val : Net; Prev_Val : Net) return Boolean + is + Inst : Instance; + begin + Inst := Get_Net_Parent (Val); + + -- Walk until the reaching Prev_Val. + loop + case Get_Id (Inst) is + when Id_Mux2 => + -- Reduce the mux. + Inst := Can_Infere_RAM_Mux2 (Inst); + if Inst = No_Instance then + return False; + end if; + when Id_Dyn_Insert + | Id_Dyn_Insert_En => + -- Skip the dyn_insert. + Inst := Get_Input_Instance (Inst, 0); + when Id_Signal + | Id_Isignal => + return Get_Output (Inst, 0) = Prev_Val; + when others => + return False; + end case; + end loop; + end Can_Infere_RAM; + + function Infere_RAM (Ctxt : Context_Acc; Val : Net) return Net + is + Inst : Instance; + begin + Inst := Get_Net_Parent (Val); + Inst := Reduce_Muxes (Ctxt, Inst); + return Get_Output (Inst, 0); + end Infere_RAM; + + pragma Unreferenced (Validate_RAM); end Netlists.Memories; diff --git a/src/synth/netlists-memories.ads b/src/synth/netlists-memories.ads index b6b487bf7..8d5e7739e 100644 --- a/src/synth/netlists-memories.ads +++ b/src/synth/netlists-memories.ads @@ -27,4 +27,11 @@ package Netlists.Memories is -- Count the number of memidx in a memory address. function Count_Memidx (Addr : Net) return Natural; + -- True iff a RAM can be infered from VAL (the input of an assignment). + -- TODO: handle partial write (offset) + -- TODO: directly check with assignment target. + function Can_Infere_RAM (Val : Net; Prev_Val : Net) return Boolean; + + -- Transform VAL to a RAM. + function Infere_RAM (Ctxt : Context_Acc; Val : Net) return Net; end Netlists.Memories; diff --git a/src/synth/netlists.adb b/src/synth/netlists.adb index c7c9edb96..7207d6ac0 100644 --- a/src/synth/netlists.adb +++ b/src/synth/netlists.adb @@ -357,7 +357,7 @@ package body Netlists is Nbr_Inputs : constant Port_Idx := Get_Nbr_Inputs (Inst); begin -- Check that all outputs are unused. - if Nbr_Outputs > 1 then + if Nbr_Outputs > 0 then for K in 0 .. Nbr_Outputs - 1 loop if Is_Connected (Get_Output (Inst, K)) then return True; @@ -861,15 +861,16 @@ package body Netlists is procedure Redirect_Inputs (Old : Net; N : Net) is First_I, I : Input; - Prev_I : Input; + Last_I : Input; begin First_I := Get_First_Sink (Old); if First_I = No_Input then + -- Nothing to do if no input. return; end if; I := First_I; - Prev_I := No_Input; + Last_I := No_Input; while I /= No_Input loop declare I_Rec : Input_Record renames Inputs_Table.Table (I); @@ -877,18 +878,16 @@ package body Netlists is pragma Assert (I_Rec.Driver = Old); I_Rec.Driver := N; - if Prev_I /= No_Input then - Inputs_Table.Table (Prev_I).Next_Sink := I; - end if; - Prev_I := I; + Last_I := I; I := I_Rec.Next_Sink; end; end loop; - if Prev_I /= No_Input then - Inputs_Table.Table (Prev_I).Next_Sink := Get_First_Sink (N); - Nets_Table.Table (N).First_Sink := First_I; - end if; + Inputs_Table.Table (Last_I).Next_Sink := Get_First_Sink (N); + Nets_Table.Table (N).First_Sink := First_I; + + -- Also disconnect OLD + Nets_Table.Table (Old).First_Sink := No_Input; end Redirect_Inputs; begin diff --git a/src/synth/synth-environment.adb b/src/synth/synth-environment.adb index 58fd0f0d8..7c3218105 100644 --- a/src/synth/synth-environment.adb +++ b/src/synth/synth-environment.adb @@ -24,10 +24,10 @@ with Netlists.Gates; with Netlists.Gates_Ports; with Netlists.Utils; use Netlists.Utils; with Netlists.Folds; use Netlists.Folds; +with Netlists.Inference; with Errorout; use Errorout; -with Synth.Inference; with Synth.Errors; use Synth.Errors; with Synth.Source; use Synth.Source; @@ -363,9 +363,11 @@ package body Synth.Environment is declare Pa : Partial_Assign_Record renames Partial_Assign_Table.Table (P); + Res : Net; begin - Inference.Infere - (Ctxt, Wid, Pa.Value, Pa.Offset, Outport, Stmt); + Res := Inference.Infere + (Ctxt, Pa.Value, Pa.Offset, Outport, Stmt); + Add_Conc_Assign (Wid, Res, Pa.Offset, Stmt); P := Pa.Next; end; end loop; @@ -1022,10 +1024,26 @@ package body Synth.Environment is if Get_Id (N1_Inst) = Id_Mux2 and then Same_Net (Get_Driver (Get_Mux2_I0 (N1_Inst)), N (0)) then - Res := Build_Mux2 - (Ctxt, Build_Dyadic (Ctxt, Id_And, - Sel, Get_Driver (Get_Mux2_Sel (N1_Inst))), - N (0), Get_Driver (Get_Mux2_I1 (N1_Inst))); + declare + N1_Net : Net; + N1_Sel : Input; + N1_Sel_Net : Net; + begin + N1_Net := Get_Output (N1_Inst, 0); + N1_Sel := Get_Input (N1_Inst, 0); + N1_Sel_Net := Get_Driver (N1_Sel); + if not Is_Connected (N1_Net) then + -- If the previous mux2 is not used, just modify it. + Res := N1_Net; + Disconnect (N1_Sel); + N1_Sel_Net := Build_Dyadic (Ctxt, Id_And, Sel, N1_Sel_Net); + Connect (N1_Sel, N1_Sel_Net); + else + Res := Build_Mux2 + (Ctxt, Build_Dyadic (Ctxt, Id_And, Sel, N1_Sel_Net), + N (0), Get_Driver (Get_Mux2_I1 (N1_Inst))); + end if; + end; else Res := Build_Mux2 (Ctxt, Sel, N (0), N (1)); end if; diff --git a/src/synth/synth-inference.adb b/src/synth/synth-inference.adb deleted file mode 100644 index 9bf2e2dbe..000000000 --- a/src/synth/synth-inference.adb +++ /dev/null @@ -1,690 +0,0 @@ --- Inference in synthesis. --- Copyright (C) 2017 Tristan Gingold --- --- This file is part of GHDL. --- --- This program is free software; you can redistribute it and/or modify --- it under the terms of the GNU General Public License as published by --- the Free Software Foundation; either version 2 of the License, or --- (at your option) any later version. --- --- This program is distributed in the hope that it will be useful, --- but WITHOUT ANY WARRANTY; without even the implied warranty of --- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the --- GNU General Public License for more details. --- --- You should have received a copy of the GNU General Public License --- along with this program; if not, write to the Free Software --- Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, --- MA 02110-1301, USA. - -with Netlists.Utils; use Netlists.Utils; -with Netlists.Gates; use Netlists.Gates; -with Netlists.Gates_Ports; use Netlists.Gates_Ports; -with Netlists.Locations; use Netlists.Locations; -with Netlists.Errors; use Netlists.Errors; -with Netlists.Internings; -with Netlists.Folds; use Netlists.Folds; - -with Synth.Flags; -with Synth.Source; use Synth.Source; -with Synth.Errors; use Synth.Errors; - -package body Synth.Inference is - -- DFF inference. - -- As an initial implementation, the following 'styles' must be - -- supported: - -- Note: rising_edge is any clock_edge; '<=' can be ':='. - -- - -- 1) - -- if rising_edge(clk) then - -- r <= x; - -- end if; - -- - -- 2) - -- if rst = '0' then - -- r <= x; - -- elsif rising_edge (clk) then - -- r <= y; - -- end if; - -- - -- 3) - -- wait until rising_edge(clk); - -- r <= x; - -- Which is equivalent to 1) when the wait statement is the only and first - -- statement, as it can be converted to an if statement. - -- - -- Netlist derived from 1) - -- +------+ - -- | | - -- | /| | - -- | |0+-+ - -- Q --+--+ | - -- |1+--- D - -- \| - -- CLK - -- This is a memorizing element as there is a loop, the value is changed - -- to D on a rising edge of the clock. - -- - -- Netlist derived from 2) - -- +------------+ - -- | /| | - -- | /| |0+-+ - -- | |0+---+ | - -- Q --+--+ | |1+----- D - -- |1+-+ \| - -- \| | CLK - -- RST +--------- '0' - -- This is a memorizing element as there is a loop. It is an asynchronous - -- reset as Q is forced to '0' when RST is asserted. - - function Has_Clock (N : Net) return Boolean - is - Inst : constant Instance := Get_Net_Parent (N); - begin - case Get_Id (Inst) is - when Id_Edge => - return True; - when Id_And => - -- Assume the condition is canonicalized, ie of the form: - -- CLK and EXPR. - -- FIXME: do it! - return Has_Clock (Get_Input_Net (Inst, 0)); - when others => - return False; - end case; - end Has_Clock; - - -- Find the longest chain of mux starting from VAL with a final input - -- of PREV_VAL. Such a chain means this is a memorising element. - -- RES is the last mux in the chain, DIST the number of mux in the chain. - procedure Find_Longest_Loop - (Val : Net; Prev_Val : Net; Res : out Instance; Dist : out Integer) - is - Inst : constant Instance := Get_Net_Parent (Val); - begin - if Get_Id (Inst) = Id_Mux2 then - declare - Res0, Res1 : Instance; - Dist0, Dist1 : Integer; - begin - if Has_Clock (Get_Driver (Get_Mux2_Sel (Inst))) then - Res := Inst; - Dist := 1; - else - Find_Longest_Loop - (Get_Driver (Get_Mux2_I0 (Inst)), Prev_Val, Res0, Dist0); - Find_Longest_Loop - (Get_Driver (Get_Mux2_I1 (Inst)), Prev_Val, Res1, Dist1); - -- Input1 has an higher priority than input0 in case - -- the selector is a clock. - -- FIXME: improve algorithm. - if Dist1 > Dist0 then - Dist := Dist1 + 1; - if Dist1 > 0 then - Res := Res1; - else - Res := Inst; - end if; - elsif Dist0 >= 0 then - Dist := Dist0 + 1; - if Dist0 > 0 then - Res := Res0; - else - Res := Inst; - end if; - else - pragma Assert (Dist1 < 0 and Dist0 < 0); - Res := No_Instance; - Dist := -1; - end if; - end if; - end; - elsif Val = Prev_Val then - Res := No_Instance; - Dist := 0; - else - Res := No_Instance; - Dist := -1; - end if; - end Find_Longest_Loop; - - procedure Extract_Clock_And (Ctxt : Context_Acc; Inst : Instance) - is - begin - pragma Assert (Get_Id (Inst) = Id_And); - - declare - I0 : constant Input := Get_Input (Inst, 0); - N0 : constant Net := Get_Driver (I0); - Inst0 : constant Instance := Get_Net_Parent (N0); - begin - case Get_Id (Inst0) is - when Id_Edge => - null; - when Id_And => - Extract_Clock_And (Ctxt, Inst0); - - -- If we have: AND convert to: AND - -- / \ / \ - -- N1 AND0 ==> AND0 EDGE - -- / \ / \ - -- N2 EDGE N1 N2 - declare - I3 : constant Input := Get_Input (Inst0, 0); - N3 : constant Net := Get_Driver (I3); - Inst3 : constant Instance := Get_Net_Parent (N3); - begin - if Get_Id (Inst3) = Id_Edge then - declare - Can_Rotate : constant Boolean := - Has_One_Connection (N0); - I2 : constant Input := Get_Input (Inst0, 1); - N2 : constant Net := Get_Driver (I2); - I1 : constant Input := Get_Input (Inst, 1); - N1 : constant Net := Get_Driver (I1); - N4 : Net; - begin - Disconnect (I0); - Disconnect (I1); - Connect (I0, N3); - if Can_Rotate then - Disconnect (I2); - Disconnect (I3); - - Connect (I1, N0); - Connect (I3, N2); - Connect (I2, N1); - else - N4 := Build_Dyadic (Ctxt, Id_And, N2, N1); - Connect (I1, N4); - end if; - end; - end if; - end; - when others => - null; - end case; - end; - - declare - I0 : constant Input := Get_Input (Inst, 1); - N0 : constant Net := Get_Driver (I0); - Inst0 : constant Instance := Get_Net_Parent (N0); - begin - case Get_Id (Inst0) is - when Id_Edge => - -- Swap inputs 0 and 1. - declare - I1 : constant Input := Get_Input (Inst, 0); - N1 : constant Net := Get_Driver (I1); - begin - Disconnect (I0); - Disconnect (I1); - Connect (I1, N0); - Connect (I0, N1); - end; - when Id_And => - Extract_Clock_And (Ctxt, Inst0); - - -- If we have: AND convert to: AND - -- / \ / \ - -- AND0 N1 ==> AND0 EDGE - -- / \ / \ - -- N2 EDGE N2 N1 - declare - I3 : constant Input := Get_Input (Inst0, 0); - N3 : constant Net := Get_Driver (I3); - begin - if Get_Id (Get_Net_Parent (N3)) = Id_Edge then - declare - Can_Rotate : constant Boolean := - Has_One_Connection (N0); - I1 : constant Input := Get_Input (Inst, 0); - N1 : constant Net := Get_Driver (I1); - N4 : Net; - begin - Disconnect (I3); - Disconnect (I1); - Connect (I1, N3); - if Can_Rotate then - Connect (I3, N1); - else - N4 := Build_Dyadic - (Ctxt, Id_And, N1, Get_Input_Net (Inst0, 1)); - Connect (I3, N4); - end if; - end; - end if; - end; - when others => - null; - end case; - end; - end Extract_Clock_And; - - -- Walk the And-net N, and extract clock (posedge/negedge) if found. - -- ENABLE is N without the clock. - -- If not found, CLK and ENABLE are set to No_Net. - procedure Extract_Clock - (Ctxt : Context_Acc; N : Net; Clk : out Net; Enable : out Net) - is - Inst : constant Instance := Get_Net_Parent (N); - begin - Clk := No_Net; - Enable := No_Net; - - case Get_Id (Inst) is - when Id_Edge => - -- Get rid of the edge gate, just return the signal. - Clk := Get_Input_Net (Inst, 0); - when Id_And => - -- Canonicalize conditions. - Extract_Clock_And (Ctxt, Inst); - - -- Condition should be in the form: CLK and EXPR - declare - I0 : constant Net := Get_Input_Net (Inst, 0); - Inst0 : constant Instance := Get_Net_Parent (I0); - begin - if Get_Id (Inst0) = Id_Edge then - -- INST is clearly not synthesizable (boolean operation on - -- an edge). Will be removed at the end by - -- remove_unused_instances. Do not remove it now as its - -- output may be used by other nets. - Clk := Get_Input_Net (Inst0, 0); - Enable := Get_Input_Net (Inst, 1); - return; - end if; - end; - when others => - null; - end case; - end Extract_Clock; - - function Is_Prev_FF_Value (V : Net; Prev_Val : Net; Off : Uns32) - return Boolean - is - Inst : Instance; - begin - if V = Prev_Val then - pragma Assert (Off = 0); - return True; - end if; - Inst := Get_Net_Parent (V); - return Get_Id (Inst) = Id_Extract - and then Get_Param_Uns32 (Inst, 0) = Off - and then Get_Input_Net (Inst, 0) = Prev_Val; - end Is_Prev_FF_Value; - - -- LAST_MUX is the mux whose input 0 is the loop and clock for selector. - function Infere_FF (Ctxt : Context_Acc; - Prev_Val : Net; - Off : Uns32; - Last_Mux : Instance; - Clk : Net; - Clk_Enable : Net; - Stmt : Source.Syn_Src) return Net - is - O : constant Net := Get_Output (Last_Mux, 0); - Data : Net; - Res : Net; - Sig : Instance; - Init : Net; - Rst : Net; - Rst_Val : Net; - Enable : Net; - begin - -- Create and return the DFF. - - -- 1. Remove the mux that creates the loop (will be replaced by the - -- dff). - declare - Sel : constant Input := Get_Mux2_Sel (Last_Mux); - I0 : constant Input := Get_Mux2_I0 (Last_Mux); - I1 : constant Input := Get_Mux2_I1 (Last_Mux); - begin - -- There must be no 'else' part for clock expression. - if not Is_Prev_FF_Value (Get_Driver (I0), Prev_Val, Off) then - Error_Msg_Synth - (+Stmt, "synchronous code does not expect else part"); - return Prev_Val; - end if; - - Disconnect (Sel); - -- Don't try to free driver of I0 as this is Prev_Val or a selection - -- of it. - Disconnect (I0); - Data := Get_Driver (I1); - -- Don't try to free driver of I1 as it is reconnected. - Disconnect (I1); - end; - - -- If the signal declaration has an initial value, get it. - Sig := Get_Net_Parent (Prev_Val); - if Get_Id (Get_Module (Sig)) = Id_Isignal then - Init := Get_Input_Net (Sig, 1); - Init := Build2_Extract (Ctxt, Init, Off, Get_Width (O)); - else - Init := No_Net; - end if; - - Enable := Clk_Enable; - - -- Look for asynchronous set/reset. They are muxes after the loop - -- mux. In theory, there can be many set/reset with a defined order. - Rst_Val := No_Net; - Rst := No_Net; - declare - Done : Boolean; - Mux : Instance; - Sel : Net; - Last_Out : Net; - Mux_Not_Rst : Net; - Mux_Rst : Net; - Mux_Rst_Val : Net; - begin - Last_Out := O; - - -- Initially, the final output is not connected. So walk from the - -- clocked mux until reaching the final output. - Done := not Is_Connected (Last_Out); - - while not Done loop - if not Has_One_Connection (Last_Out) - and then not Is_Const_Net (Last_Out) - then - -- TODO. - raise Internal_Error; - end if; - - -- The parent must be a mux (it's a chain of muxes). - Mux := Get_Input_Parent (Get_First_Sink (Last_Out)); - pragma Assert (Get_Id (Mux) = Id_Mux2); - - -- Extract the reset condition and the reset value. - Sel := Get_Driver (Get_Mux2_Sel (Mux)); - if Get_Driver (Get_Mux2_I0 (Mux)) = Last_Out then - Mux_Rst_Val := Get_Driver (Get_Mux2_I1 (Mux)); - Mux_Rst := Sel; - elsif Get_Driver (Get_Mux2_I1 (Mux)) = Last_Out then - Mux_Rst_Val := Get_Driver (Get_Mux2_I0 (Mux)); - Mux_Rst := Build_Monadic (Ctxt, Id_Not, Sel); - else - -- Cannot happen. - raise Internal_Error; - end if; - - Last_Out := Get_Output (Mux, 0); - Done := not Is_Connected (Last_Out); - - if Is_Prev_FF_Value (Mux_Rst_Val, Prev_Val, Off) then - -- The mux is like an enable. Like in this example, q2 is not - -- assigned when RST is true: - -- if rst then - -- q1 <= '0'; - -- elsif rising_edge(clk) then - -- q2 <= d2; - -- q1 <= d1; - -- end if; - - -- Remove the mux - Disconnect (Get_Mux2_I0 (Mux)); - Disconnect (Get_Mux2_I1 (Mux)); - Disconnect (Get_Mux2_Sel (Mux)); - - -- Add the negation of the condition to the enable signal. - -- Negate the condition for the current reset. - Mux_Not_Rst := Build_Monadic (Ctxt, Id_Not, Mux_Rst); - if Rst /= No_Net then - Rst := Build_Dyadic (Ctxt, Id_And, Rst, Mux_Not_Rst); - end if; - if Enable = No_Net then - Enable := Mux_Not_Rst; - else - Enable := Build_Dyadic (Ctxt, Id_And, Enable, Mux_Not_Rst); - end if; - else - -- Assume this is a reset value. - -- FIXME: check for no logical loop. - - if Rst = No_Net then - -- Remove the last mux. Dedicated inputs on the FF - -- are used. - Disconnect (Get_Mux2_I0 (Mux)); - Disconnect (Get_Mux2_I1 (Mux)); - Disconnect (Get_Mux2_Sel (Mux)); - - -- The output of the mux is now the reset value. - Redirect_Inputs (Last_Out, Mux_Rst_Val); - Free_Instance (Mux); - - Rst := Mux_Rst; - Rst_Val := Mux_Rst_Val; - Last_Out := Mux_Rst_Val; - else - Rst := Build_Dyadic (Ctxt, Id_Or, Mux_Rst, Rst); - Rst_Val := Last_Out; - end if; - end if; - end loop; - end; - - -- If there is a condition with the clock, that's an enable which - -- keep the previous value if the condition is false. Add the mux - -- for it. - if Enable /= No_Net then - declare - Prev : Net; - begin - Prev := Build2_Extract (Ctxt, Prev_Val, Off, Get_Width (Data)); - - Data := Build_Mux2 (Ctxt, Enable, Prev, Data); - Copy_Location (Data, Enable); - end; - end if; - - -- Create the FF. - if Rst = No_Net then - pragma Assert (Rst_Val = No_Net); - if Init /= No_Net then - Res := Build_Idff (Ctxt, Clk, D => Data, Init => Init); - else - Res := Build_Dff (Ctxt, Clk, D => Data); - end if; - else - if Init /= No_Net then - Res := Build_Iadff (Ctxt, Clk, D => Data, - Rst => Rst, Rst_Val => Rst_Val, - Init => Init); - else - Res := Build_Adff (Ctxt, Clk, D => Data, - Rst => Rst, Rst_Val => Rst_Val); - end if; - end if; - Copy_Location (Res, Last_Mux); - - -- The output of the mux may be read later in the process, - -- like this: - -- if clk'event and clk = '1' then - -- d := i + 1; - -- end if; - -- d1 := d + 1; - -- So connections to the mux output are redirected to dff - -- output. - Redirect_Inputs (O, Res); - - Free_Instance (Last_Mux); - - return Res; - end Infere_FF; - - -- Detect false combinational loop. They can easily appear when variables - -- are only used in one branch: - -- process (all) - -- variable a : std_logic; - -- begin - -- r <= '1'; - -- if sel = '1' then - -- a := '1'; - -- r <= '0'; - -- end if; - -- end process; - -- There is a combinational path from 'a' to 'a' as - -- a := (sel = '1') ? '1' : a; - -- But this is a false loop because the value of 'a' is never used. In - -- that case, 'a' is assigned to 'x' and all the unused logic will be - -- removed during clean-up. - -- - -- Detection is very simple: the closure of readers of 'a' must be only - -- muxes (which were inserted by controls). - function Is_False_Loop (Prev_Val : Net) return Boolean - is - package Inst_Interning renames - Netlists.Internings.Dyn_Instance_Interning; - use Inst_Interning; - T : Inst_Interning.Instance; - - function Add_From_Net (N : Net) return Boolean - is - Inst : Netlists.Instance; - Inp : Input; - begin - Inp := Get_First_Sink (N); - while Inp /= No_Input loop - Inst := Get_Input_Parent (Inp); - if Get_Id (Inst) not in Mux_Module_Id then - return False; - end if; - - -- Add to T (if not already). - Get (T, Inst, Inst); - - Inp := Get_Next_Sink (Inp); - end loop; - - return True; - end Add_From_Net; - - function Walk_Nets (N : Net) return Boolean - is - Inst : Netlists.Instance; - begin - -- Put gates that read the value. - if not Add_From_Net (N) then - return False; - end if; - - -- Follow the outputs. - for I in First_Index .. Index_Type'Last loop - exit when I > Inst_Interning.Last_Index (T); - Inst := Get_By_Index (T, I); - if not Add_From_Net (Get_Output (Inst, 0)) then - return False; - end if; - end loop; - - -- No external readers. - return True; - end Walk_Nets; - - Res : Boolean; - begin - Inst_Interning.Init (T); - - Res := Walk_Nets (Prev_Val); - - Inst_Interning.Free (T); - - return Res; - end Is_False_Loop; - - function Infere_Latch (Ctxt : Context_Acc; - Val : Net; - Prev_Val : Net; - Stmt : Source.Syn_Src) return Net - is - Name : Sname; - begin - -- In case of false loop, do not close the loop but assign X. - if Is_False_Loop (Prev_Val) then - return Build_Const_X (Ctxt, Get_Width (Val)); - end if; - - -- Latch or combinational loop. - if Get_Id (Get_Net_Parent (Prev_Val)) = Id_Output then - -- Outputs are connected to a port. The port is the first connection - -- made, so it is the last sink. Be more tolerant and look for - -- the (only) port connected to the output. - declare - Inp : Input; - Inst : Instance; - begin - Inp := Get_First_Sink (Prev_Val); - loop - pragma Assert (Inp /= No_Input); - Inst := Get_Input_Parent (Inp); - if Get_Id (Inst) >= Id_User_None then - Name := Get_Output_Desc (Get_Module (Inst), - Get_Port_Idx (Inp)).Name; - exit; - end if; - Inp := Get_Next_Sink (Inp); - end loop; - end; - else - Name := Get_Instance_Name (Get_Net_Parent (Prev_Val)); - end if; - Error_Msg_Synth (+Stmt, "latch infered for net %n", +Name); - - return Val; - end Infere_Latch; - - -- Note: PREV_VAL is the wire gate, so with full width and no offset. - procedure Infere (Ctxt : Context_Acc; - Wid : Wire_Id; - Val : Net; - Off : Uns32; - Prev_Val : Net; - Stmt : Source.Syn_Src) - is - pragma Assert (Val /= No_Net); - pragma Assert (Prev_Val /= No_Net); - Last_Mux : Instance; - Len : Integer; - Sel : Input; - Clk : Net; - Enable : Net; - Res : Net; - begin - if not Flags.Flag_Debug_Noinference then - if Get_First_Sink (Prev_Val) = No_Input then - -- PREV_VAL is never read, so there cannot be any loop. - -- This is an important optimization for control signals. - Len := -1; - else - Find_Longest_Loop (Val, Prev_Val, Last_Mux, Len); - end if; - else - Len := -1; - end if; - if Len <= 0 then - -- No logical loop or self assignment. - Res := Val; - else - -- So there is a logical loop. - Sel := Get_Mux2_Sel (Last_Mux); - Extract_Clock (Ctxt, Get_Driver (Sel), Clk, Enable); - if Clk = No_Net then - -- No clock -> latch or combinational loop - Res := Infere_Latch (Ctxt, Val, Prev_Val, Stmt); - else - -- Clock -> FF - Res := Infere_FF (Ctxt, Prev_Val, Off, Last_Mux, - Clk, Enable, Stmt); - end if; - end if; - - Add_Conc_Assign (Wid, Res, Off, Stmt); - end Infere; -end Synth.Inference; diff --git a/src/synth/synth-inference.ads b/src/synth/synth-inference.ads deleted file mode 100644 index 377b481ab..000000000 --- a/src/synth/synth-inference.ads +++ /dev/null @@ -1,37 +0,0 @@ --- Inference in synthesis. --- Copyright (C) 2017 Tristan Gingold --- --- This file is part of GHDL. --- --- This program is free software; you can redistribute it and/or modify --- it under the terms of the GNU General Public License as published by --- the Free Software Foundation; either version 2 of the License, or --- (at your option) any later version. --- --- This program is distributed in the hope that it will be useful, --- but WITHOUT ANY WARRANTY; without even the implied warranty of --- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the --- GNU General Public License for more details. --- --- You should have received a copy of the GNU General Public License --- along with this program; if not, write to the Free Software --- Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, --- MA 02110-1301, USA. - -with Types; use Types; -with Netlists; use Netlists; -with Netlists.Builders; use Netlists.Builders; -with Synth.Environment; use Synth.Environment; -with Synth.Source; - -package Synth.Inference is - -- To be called when there is an assignment to a signal/output of VAL and - -- the previous value is PREV_VAL (an Id_Signal or Id_Output). - -- If there is a loop, infere a dff or a latch or emit an error. - procedure Infere (Ctxt : Context_Acc; - Wid : Wire_Id; - Val : Net; - Off : Uns32; - Prev_Val : Net; - Stmt : Source.Syn_Src); -end Synth.Inference; -- cgit v1.2.3