-- Extract memories. -- Copyright (C) 2019 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, see . with Ada.Unchecked_Deallocation; with Errorout; use Errorout; with Grt.Algos; with Netlists.Gates; use Netlists.Gates; with Netlists.Utils; use Netlists.Utils; 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; package body Netlists.Memories is -- If set, be verbose why a memory is not found. But the messages are -- a little bit cryptic. Flag_Memory_Verbose : constant Boolean := False; -- TODO: -- * Add an offset to Id_Mem_Wr_Sync to handle partial write, -- and do not create multiple memories in case of partial writes. This -- will allow a representation closer to the Yosys one. -- * Handle multi-dim memories with some fixed addresses. Here we need -- to split a memory into multiple ones. -- * Improve detection of synchronous read ports. See mem03/ -- What is a memory ? -- -- A memory is obviously a memorizing element. This means there is a -- logical loop between input and output. Because there is a loop, a -- name is required in the HDL input to create a loop. You cannot create -- a memory without a signal/variable name (but you can create a ROM -- without it). -- TODO: can it be proved ? -- -- A memory is not a flip-flop nor a latch. The reason is that only a -- part of the memory is worked on. Only a part of the memory is read, -- and only a part of the memory is written (but a variable part). -- So, the logical loop is modified by using dyn_insert and read by -- using dyn_extract. And muxes. -- -- HDL structure of a memory (RAM). -- -- A memory can be only be read or written partially, using either an -- indexed name of a slice. -- -- Example1: -- val1 := mem (addr1) -- Example2: -- mem (addr2) <= val2; -- -- A read generates a dyn_extract, while a write generates a dyn_insert. -- -- It is possible to use a write enable, which is synthesized as a mux. -- -- Example3: -- if en then -- mem (addr3) <= val3; -- end if; -- -- So a dyn_insert can be followed by a mux, using these connections: -- _ -- / |----- dyn_insert ----+----+ -- out --| | | +---- inp -- \_|---------------------/ -- -- There might be several muxes, but using the same input when not -- selecting the dyn_insert. They could be merged. -- -- Additionally, a mux can also select between two writes. -- -- Example4: -- if sel then -- mem (addr4a) <= val4a; -- else -- mem (addr4b) <= val4b; -- end if; -- -- The netlist generated for this structure is: -- _ -- / |----- dyn_insert ----\ -- out --| | +--------- inp -- \_|----- dyn_insert ----/ -- -- Note: a Dff may have replaced a mux if the enable is a clock edge. -- -- Any write can be followed by another write. Can be a dual-port memory, -- of write to different bytes. -- -- Example5: -- mem(addr5a) <= val5a; -- mem(addr5b) <= val5b; -- -- So, there can be a combination any of these elements, each having -- one input and one output. -- - O := dyn_insert(I) -- - O := mux(sel, el(I), I) -- - O := mux(sel, el1(I), el2(I)) -- - O := el1(el2(I)) -- -- -- Reads can happen anywhere. But we will first consider only reads -- that occurs just after the dff (so synchronous reads) or just before -- the dff (asynchronous reads). -- -- If there is another logical element, then this is not a memory. -- -- How rams/roms are detected ? -- All dyn_extract/dyn_insert are gathered, and walked to the signal. -- Then all those signals are gathered: that's the candidate memories. -- -- How rams/roms are qualified (from candidate memories to memories) ? -- There must be only dyn_insert/dyn_extract + muxes on the logical loop. -- Use a mark algorithm. -- -- Once qualified: -- Merge muxes to the dyn_inserts. -- FIXME: position of dyn_extract wrt dyn_insert: -- if en then -- mem(ad1) := val1; -- val2 := mem(ad2); -- end if; -- -- Strategy: merge muxes until the logical loop is only composed of -- dyn_insert/dyn_extract (+ signal and maybe dff). -- Follow signal from ORIG to discover memory ports size. -- Should be the same. procedure Check_Memory_Read_Ports (Orig : Instance; Data_W : out Width; Size : out Width) is Orig_Net : constant Net := Get_Output (Orig, 0); W : Width; begin -- By default, error. Data_W := 0; Size := 0; -- Check readers. declare Inp : Input; Extr_Inst : Instance; Idx : Instance; Step : Uns32; begin Inp := Get_First_Sink (Orig_Net); while Inp /= No_Input loop Extr_Inst := Get_Input_Parent (Inp); case Get_Id (Extr_Inst) is when Id_Dyn_Extract => -- Extract step from memidx gate. Idx := Get_Net_Parent (Get_Input_Net (Extr_Inst, 1)); while Get_Id (Idx) = Id_Addidx loop -- Multi-dim arrays, lowest index is the last one. Idx := Get_Net_Parent (Get_Input_Net (Idx, 1)); end loop; pragma Assert (Get_Id (Idx) = Id_Memidx); Step := Get_Param_Uns32 (Idx, 0); -- Check offset if Get_Param_Uns32 (Extr_Inst, 0) /= 0 then Info_Msg_Synth (+Extr_Inst, "partial read from memory %n", (1 => +Orig)); Data_W := 0; return; end if; -- Check data width. W := Get_Width (Get_Output (Extr_Inst, 0)); pragma Assert (W > 0); if W > Step then Info_Msg_Synth (+Extr_Inst, "overlapping read from memory %n", (1 => +Orig)); Data_W := 0; return; end if; if Data_W = 0 then pragma Assert (Step /= 0); Data_W := Step; elsif Data_W /= Step then Info_Msg_Synth (+Extr_Inst, "read from memory %n with different size", (1 => +Orig)); Data_W := 0; return; end if; when Id_Dyn_Insert | Id_Dyn_Insert_En | Id_Mux2 => -- Probably a writer. -- FIXME: check it has already been by writes. null; when others => Info_Msg_Synth (+Extr_Inst, "full read from memory %n", (1 => +Orig)); Data_W := 0; return; end case; Inp := Get_Next_Sink (Inp); end loop; end; if Data_W = 0 then Info_Msg_Synth (+Orig, "memory %n is never read", (1 => +Orig)); Data_W := 0; else Size := Get_Width (Orig_Net) / Data_W; end if; end Check_Memory_Read_Ports; -- Count the number of memidx in a memory address. function Count_Memidx (Addr : Net) return Natural is N : Net; Inst : Instance; Res : Natural; begin N := Addr; Res := 0; loop Inst := Get_Net_Parent (N); case Get_Id (Inst) is when Id_Memidx => return Res + 1; when Id_Addidx => if Get_Id (Get_Input_Instance (Inst, 1)) /= Id_Memidx then raise Internal_Error; end if; Res := Res + 1; N := Get_Input_Net (Inst, 0); when Id_Const_X => -- For a null wire. pragma Assert (Res = 0); pragma Assert (Get_Width (N) = 0); return 0; when others => raise Internal_Error; end case; end loop; end Count_Memidx; -- Lower memidx/addidx to simpler gates (concat). -- MEM_SIZE: size of the memory (in bits). -- ADDR is the address net with memidx/addidx gates. -- VAL_WD is the width of the data port. procedure Convert_Memidx (Ctxt : Context_Acc; Mem_Size : Uns32; Addr : in out Net; Val_Wd : Width) is -- Number of memidx. Nbr_Idx : constant Positive := Count_Memidx (Addr); Can_Free : constant Boolean := not Is_Connected (Addr); Mem_Depth : Uns32; Last_Size : Uns32; Low_Addr : Net; type Idx_Data is record Inst : Instance; Addr : Net; end record; type Idx_Array is array (Natural range <>) of Idx_Data; Indexes : Idx_Array (1 .. Nbr_Idx); begin -- Fill the INDEXES array. -- The convention is that input 0 of addidx is a memidx. declare P : Natural; N : Net; Inst : Instance; Inst2 : Instance; begin N := Addr; P := 0; loop Inst := Get_Net_Parent (N); case Get_Id (Inst) is when Id_Memidx => P := P + 1; Indexes (P) := (Inst => Inst, Addr => No_Net); exit; when Id_Addidx => Inst2 := Get_Input_Instance (Inst, 0); if Get_Id (Inst2) /= Id_Memidx then raise Internal_Error; end if; P := P + 1; Indexes (P) := (Inst => Inst2, Addr => No_Net); N := Get_Input_Net (Inst, 1); when others => raise Internal_Error; end case; end loop; pragma Assert (P = Nbr_Idx); end; -- Memory size is a multiple of data width. -- FIXME: doesn't work if only a part of the reg is a memory. if Mem_Size mod Val_Wd /= 0 then raise Internal_Error; end if; Mem_Depth := Mem_Size / Val_Wd; pragma Unreferenced (Mem_Depth); -- Do checks on memidx. Last_Size := Mem_Size; for I in Indexes'Range loop declare Inst : constant Instance := Indexes (I).Inst; Step : constant Uns32 := Get_Param_Uns32 (Inst, 0); Sub_Addr : constant Net := Get_Input_Net (Inst, 0); Addr_W : constant Width := Get_Width (Sub_Addr); Max : constant Uns32 := Get_Param_Uns32 (Inst, 1); Max_W : constant Width := Clog2 (Max + 1); Sub_Addr1 : Net; Sz : Uns32; begin -- Check max (from previous dimension). -- Check the memidx can index its whole input. pragma Assert (Max /= 0); Sz := (Max + 1) * Step; if Sz /= Last_Size then raise Internal_Error; end if; Last_Size := Step; if I = Indexes'Last then if Step /= Val_Wd then raise Internal_Error; end if; end if; -- Check addr width. if Addr_W = 0 then raise Internal_Error; end if; if Addr_W > Max_W then -- Need to truncate. Sub_Addr1 := Build2_Trunc (Ctxt, Id_Utrunc, Sub_Addr, Max_W, Get_Location (Inst)); else Sub_Addr1 := Sub_Addr; end if; Indexes (I).Addr := Sub_Addr1; end; end loop; -- Lower (just concat addresses). declare use Netlists.Concats; Concat : Concat_Type; begin for I in reverse Indexes'Range loop Append (Concat, Indexes (I).Addr); end loop; Build (Ctxt, Concat, Low_Addr); end; -- Free addidx and memidx. if Can_Free then declare N : Net; Inp : Input; Inst : Instance; Inst2 : Instance; begin N := Addr; loop Inst := Get_Net_Parent (N); case Get_Id (Inst) is when Id_Memidx => Inp := Get_Input (Inst, 0); Disconnect (Inp); Remove_Instance (Inst); exit; when Id_Addidx => -- Remove the first input (a memidx). Inp := Get_Input (Inst, 0); Inst2 := Get_Net_Parent (Get_Driver (Inp)); pragma Assert (Get_Id (Inst2) = Id_Memidx); Disconnect (Inp); Inp := Get_Input (Inst2, 0); Disconnect (Inp); Remove_Instance (Inst2); -- Continue with the second input. Inp := Get_Input (Inst, 1); N := Get_Driver (Inp); Disconnect (Inp); -- Remove the addidx. Remove_Instance (Inst); when others => raise Internal_Error; end case; end loop; end; end if; Addr := Low_Addr; end Convert_Memidx; procedure Convert_Memidx (Ctxt : Context_Acc; Mem : Instance; Addr : in out Net; Val_Wd : Width) is Mem_Size : constant Uns32 := Get_Width (Get_Output (Mem, 0)); begin Convert_Memidx (Ctxt, Mem_Size, Addr, Val_Wd); end Convert_Memidx; -- Return True iff MUX_INP is a mux2 input whose output is connected to a -- dff to create a DFF with enable (the other mux2 input is connected to -- the dff output). function Is_Enable_Dff (Mux_Inp : Input) return Boolean is Mux_Inst : constant Instance := Get_Input_Parent (Mux_Inp); pragma Assert (Get_Id (Mux_Inst) = Id_Mux2); Mux_Out : constant Net := Get_Output (Mux_Inst, 0); Inp : Input; Dff_Inst : Instance; Dff_Out : Net; begin Inp := Get_First_Sink (Mux_Out); if Inp = No_Input or else Get_Next_Sink (Inp) /= No_Input then -- The output of the mux must be connected to one input. return False; end if; Dff_Inst := Get_Input_Parent (Inp); if Get_Id (Dff_Inst) /= Id_Dff then return False; end if; Dff_Out := Get_Output (Dff_Inst, 0); if Mux_Inp = Get_Input (Mux_Inst, 1) then return Skip_Signal (Get_Input_Net (Mux_Inst, 2)) = Dff_Out; else return Skip_Signal (Get_Input_Net (Mux_Inst, 1)) = Dff_Out; end if; end Is_Enable_Dff; -- INST is a Dyn_Extract. -- If INST is followed by a dff or a dff+enable (with mux2), return the -- dff in LAST_INST, the clock in CLK and the enable in EN. procedure Extract_Extract_Dff (Ctxt : Context_Acc; Inst : Instance; Last_Inst : out Instance; Clk : out Net; En : out Net) is Val : constant Net := Get_Output (Inst, 0); Inp : Input; Iinst : Instance; begin Inp := Get_First_Sink (Val); if Get_Next_Sink (Inp) = No_Input then -- There is a single input. Iinst := Get_Input_Parent (Inp); if Get_Id (Iinst) = Id_Dff then -- The output of the dyn_extract is directly connected to a dff. -- So this is a synchronous read without enable. declare Clk_Inp : Input; begin Clk_Inp := Get_Input (Iinst, 0); Clk := Get_Driver (Clk_Inp); Disconnect (Clk_Inp); En := No_Net; Disconnect (Inp); Last_Inst := Iinst; return; end; elsif Get_Id (Iinst) = Id_Mux2 and then Is_Enable_Dff (Inp) then declare Mux_Out : constant Net := Get_Output (Iinst, 0); Mux_En_Inp : constant Input := Get_Input (Iinst, 0); Mux_I0_Inp : constant Input := Get_Input (Iinst, 1); Mux_I1_Inp : constant Input := Get_Input (Iinst, 2); Dff_Din : constant Input := Get_First_Sink (Mux_Out); Dff_Inst : constant Instance := Get_Input_Parent (Dff_Din); Dff_Out : constant Net := Get_Output (Dff_Inst, 0); Clk_Inp : constant Input := Get_Input (Dff_Inst, 0); begin Clk := Get_Driver (Clk_Inp); En := Get_Driver (Mux_En_Inp); if Dff_Out = Get_Driver (Mux_I1_Inp) then En := Build_Monadic (Ctxt, Id_Not, En); Copy_Location (En, Iinst); end if; Disconnect (Mux_En_Inp); Disconnect (Mux_I0_Inp); Disconnect (Mux_I1_Inp); Disconnect (Dff_Din); Disconnect (Clk_Inp); Remove_Instance (Iinst); Last_Inst := Dff_Inst; return; end; end if; end if; Last_Inst := Inst; Clk := No_Net; En := No_Net; end Extract_Extract_Dff; -- If dyn_extract gate EXTRACT is followed by a concat and a dff, then -- swap the dff and the concat. This will allow to merge the dff during -- the build of mem_rd_sync. -- This creates new gates (the dff is replicated) that will be removed. procedure Maybe_Swap_Concat_Mux_Dff (Ctxt : Context_Acc; Extract : Instance) is Extr_Out : constant Net := Get_Output (Extract, 0); Concat : Instance; Concat_Out : Net; Dff : Instance; Clk, En : Net; Loc : Location_Type; begin if not Has_One_Connection (Extr_Out) then -- The dyn_extract is connected to more than one gate. return; end if; Concat := Get_Input_Parent (Get_First_Sink (Extr_Out)); case Get_Id (Concat) is when Concat_Module_Id | Id_Concatn => null; when others => -- Not a concat. return; end case; Concat_Out := Get_Output (Concat, 0); if not Has_One_Connection (Concat_Out) then -- The concat is connected to more than one gate. return; end if; for I in 1 .. Get_Nbr_Inputs (Concat) loop declare Src : constant Net := Get_Input_Net (Concat, I - 1); begin if Get_Id (Get_Net_Parent (Src)) /= Id_Dyn_Extract then -- A source of concat is not a dyn_extract. return; end if; if not Has_One_Connection (Src) then -- A source of concat drives something else! return; end if; end; end loop; Extract_Extract_Dff (Ctxt, Concat, Dff, Clk, En); if Clk = No_Net then return; end if; -- Replicate the dff. Loc := Get_Location (Dff); for I in 1 .. Get_Nbr_Inputs (Concat) loop declare Inp : constant Input := Get_Input (Concat, I - 1); Dff2 : Net; Mux : Net; Dff2_Inp : Input; Src : Net; begin Src := Disconnect_And_Get (Inp); Dff2 := Build_Dff (Ctxt, Clk, Src); Set_Location (Dff2, Loc); Connect (Inp, Dff2); if En /= No_Net then Dff2_Inp := Get_Input (Get_Net_Parent (Dff2), 1); Mux := Build_Mux2 (Ctxt, En, Dff2, Src); Set_Location (Mux, Loc); Disconnect (Dff2_Inp); Connect (Dff2_Inp, Mux); end if; end; end loop; -- Reconnect the concat. Redirect_Inputs (Get_Output (Dff, 0), Concat_Out); Remove_Instance (Dff); end Maybe_Swap_Concat_Mux_Dff; procedure Maybe_Swap_Mux_Concat_Dff (Ctxt : Context_Acc; Extract : Instance) is Concat : Instance; Concat_Out : Net; Dff : Instance; Dff_Inp : Input; Dff_Out : Net; Dff_Off : Uns32; Clk, En : Net; Loc : Location_Type; begin declare Extr_Out : constant Net := Get_Output (Extract, 0); Mux_Inp : Input; Mux : Instance; Mux_Out : Net; Concat_Inp : Input; begin if not Has_One_Connection (Extr_Out) then -- The dyn_extract is connected to more than one gate. return; end if; -- The output is connected to a Mux2. Mux_Inp := Get_First_Sink (Extr_Out); Mux := Get_Input_Parent (Mux_Inp); if Get_Id (Mux) /= Id_Mux2 then -- Not a mux2. return; end if; Mux_Out := Get_Output (Mux, 0); if not Has_One_Connection (Mux_Out) then return; end if; -- The Mux2 output is connected to a concat. Concat_Inp := Get_First_Sink (Mux_Out); Concat := Get_Input_Parent (Concat_Inp); case Get_Id (Concat) is when Concat_Module_Id | Id_Concatn => null; when others => -- Not a concat. return; end case; -- The concat is connected to a dff. Concat_Out := Get_Output (Concat, 0); if not Has_One_Connection (Concat_Out) then -- The concat is connected to more than one gate. return; end if; Dff_Inp := Get_First_Sink (Concat_Out); Dff := Get_Input_Parent (Dff_Inp); if Get_Id (Dff) /= Id_Dff then return; end if; end; -- Check all concat inputs are connected to a mux2, which is -- connected to a dyn_extract. Dff_Out := Get_Output (Dff, 0); Dff_Off := 0; for I in reverse 1 .. Get_Nbr_Inputs (Concat) loop declare Mux_Net : constant Net := Get_Input_Net (Concat, I - 1); Mux_Inst : constant Instance := Get_Net_Parent (Mux_Net); Extr_Net : Net; Extr_Inst : Instance; begin if Get_Id (Mux_Inst) /= Id_Mux2 then return; end if; if not Has_One_Connection (Mux_Net) then -- A source of concat drives something else! return; end if; Extr_Net := Get_Input_Net (Mux_Inst, 2); if Get_Id (Get_Net_Parent (Extr_Net)) /= Id_Dyn_Extract then -- A source of concat is not a dyn_extract. return; end if; if not Has_One_Connection (Extr_Net) then -- A source of concat drives something else! return; end if; -- Check the Mux2 is a enable for the dff. Extr_Net := Get_Input_Net (Mux_Inst, 1); Extr_Inst := Get_Net_Parent (Extr_Net); if Get_Id (Extr_Inst) /= Id_Extract then return; end if; if Get_Param_Uns32 (Extr_Inst, 0) /= Dff_Off then return; end if; if Get_Input_Net (Extr_Inst, 0) /= Dff_Out then return; end if; Dff_Off := Dff_Off + Get_Width (Mux_Net); end; end loop; Extract_Extract_Dff (Ctxt, Concat, Dff, Clk, En); if Clk = No_Net then return; end if; -- There is no additional enabler for the dff. pragma Assert (En = No_Net); -- Replicate the dff. Loc := Get_Location (Dff); for I in 1 .. Get_Nbr_Inputs (Concat) loop declare Inp : constant Input := Get_Input (Concat, I - 1); Dff2 : Net; Mux_Inst2 : Instance; Mux_Inp2 : Input; Src : Net; Extr_Out2 : Net; Extr_Inst2 : Instance; begin -- Disconnect the mux2. Src := Disconnect_And_Get (Inp); Dff2 := Build_Dff (Ctxt, Clk, Src); Set_Location (Dff2, Loc); Connect (Inp, Dff2); Mux_Inst2 := Get_Net_Parent (Src); Mux_Inp2 := Get_Input (Mux_Inst2, 1); Extr_Out2 := Disconnect_And_Get (Mux_Inp2); Connect (Mux_Inp2, Dff2); Extr_Inst2 := Get_Net_Parent (Extr_Out2); Disconnect (Get_Input (Extr_Inst2, 0)); Remove_Instance (Extr_Inst2); end; end loop; -- Reconnect the concat. Redirect_Inputs (Get_Output (Dff, 0), Concat_Out); Remove_Instance (Dff); end Maybe_Swap_Mux_Concat_Dff; -- Generic procedure to call CB on each memory future port (dyn_insert -- or dyn_extract). generic type Data_Type is private; with procedure Cb (Inst : Instance; Data : in out Data_Type; Fail : out Boolean); procedure Foreach_Port (Sig : Instance; Data : in out Data_Type); procedure Foreach_Port (Sig : Instance; Data : in out Data_Type) is Fail : Boolean; Inst, Inst2 : Instance; Inp2 : Input; begin -- Top-level loop, for each parallel path of multiport RAMs. Inp2 := Get_First_Sink (Get_Output (Sig, 0)); while Inp2 /= No_Input loop Inst2 := Get_Input_Parent (Inp2); case Get_Id (Inst2) is when Id_Dyn_Extract => Cb (Inst2, Data, Fail); if Fail then return; end if; when Id_Dyn_Insert | Id_Dyn_Insert_En => Cb (Inst2, Data, Fail); if Fail then return; end if; -- Walk till the signal. Inst := Inst2; loop declare Inp : Input; N_Inst : Instance; In_Inst : Instance; begin -- Check gates connected to the output. Inp := Get_First_Sink (Get_Output (Inst, 0)); N_Inst := No_Instance; while Inp /= No_Input loop In_Inst := Get_Input_Parent (Inp); case Get_Id (In_Inst) is when Id_Dyn_Extract => Cb (In_Inst, Data, Fail); if Fail then return; end if; when Id_Dyn_Insert_En | Id_Dyn_Insert => Cb (In_Inst, Data, Fail); if Fail then return; end if; pragma Assert (N_Inst = No_Instance); N_Inst := In_Inst; when Id_Signal | Id_Isignal | Id_Mem_Multiport | Id_Dff | Id_Idff => pragma Assert (N_Inst = No_Instance); N_Inst := In_Inst; when Id_Mdff | Id_Midff => if Inp = Get_Input (In_Inst, 1) then pragma Assert (N_Inst = No_Instance); N_Inst := In_Inst; end if; when others => raise Internal_Error; end case; Inp := Get_Next_Sink (Inp); end loop; Inst := N_Inst; exit when Inst = Sig; end; end loop; when others => raise Internal_Error; end case; Inp2 := Get_Next_Sink (Inp2); end loop; end Foreach_Port; type Gather_Ports_Type is record Ports : Instance_Array_Acc; Nports : Nat32; end record; procedure Gather_Ports_Cb (Inst : Instance; Data : in out Gather_Ports_Type; Fail : out Boolean) is begin Data.Nports := Data.Nports + 1; Data.Ports (Data.Nports) := Inst; Fail := False; end Gather_Ports_Cb; procedure Gather_Ports_Foreach is new Foreach_Port (Data_Type => Gather_Ports_Type, Cb => Gather_Ports_Cb); -- Fill PORTS with all the ports from the SIG chain. procedure Gather_Ports (Sig : Instance; Ports : Instance_Array_Acc) is Data : Gather_Ports_Type; begin Data := (Ports, 0); Gather_Ports_Foreach (Sig, Data); pragma Assert (Data.Nports = Ports'Last); end Gather_Ports; -- Check if the index of Memidx MIDX is of the form: MAX - off, -- where MAX is the maximum value of off. function Is_Reverse_Range (Midx : Instance) return Boolean is pragma Assert (Get_Id (Midx) = Id_Memidx); Sub : constant Instance := Get_Input_Instance (Midx, 0); Val : Instance; begin if Get_Id (Sub) /= Id_Sub then return False; end if; Val := Get_Input_Instance (Sub, 0); if Get_Id (Val) /= Id_Const_UB32 then return False; end if; return Get_Param_Uns32 (Val, 0) = Get_Param_Uns32 (Midx, 1); end Is_Reverse_Range; -- Direction TO in address port generates a sub (as vectors are normalized -- on the DOWNTO direction). Simply remap the memory by removing all the -- subs. procedure Maybe_Remap_Address (Ctxt : Context_Acc; Sig : Instance; Nbr_Ports : Nat32) is pragma Unreferenced (Ctxt); Ports : Instance_Array_Acc; begin Ports := new Instance_Array (1 .. Nbr_Ports); -- 1. Gather all ports. Gather_Ports (Sig, Ports); -- 2. From ports, get the index. for I in Ports'Range loop declare P : constant Instance := Ports (I); Idx : Input; begin case Get_Id (P) is when Id_Dyn_Extract => Idx := Get_Input (P, 1); when Id_Dyn_Insert | Id_Dyn_Insert_En => Idx := Get_Input (P, 2); when others => raise Internal_Error; end case; Ports (I) := Get_Net_Parent (Get_Driver (Idx)); end; end loop; -- 3. For each dimension loop declare M : Instance; Done : Boolean; Idx : Net; Is_Reverse : Boolean; W : Width; Step : Uns32; Max : Uns32; begin Done := False; for I in Ports'Range loop -- Get the index (memidx gate). M := Ports (I); case Get_Id (M) is when Id_Memidx => null; when Id_Addidx => M := Get_Input_Instance (M, 0); pragma Assert (Get_Id (M) = Id_Memidx); when others => raise Internal_Error; end case; Idx := Get_Input_Net (M, 0); if I = 1 then W := Get_Width (Idx); Step := Get_Param_Uns32 (M, 0); Max := Get_Param_Uns32 (M, 1); Is_Reverse := Is_Reverse_Range (M); else if Get_Width (Idx) /= W or else Get_Param_Uns32 (M, 0) /= Step or else Get_Param_Uns32 (M, 1) /= Max or else Is_Reverse_Range (M) /= Is_Reverse then -- Different width, steps or direction. Done := True; exit; end if; end if; end loop; exit when Done; -- Update ports. for I in Ports'Range loop M := Ports (I); case Get_Id (M) is when Id_Memidx => Ports (I) := No_Instance; Done := True; when Id_Addidx => Ports (I) := Get_Input_Instance (M, 1); M := Get_Input_Instance (M, 0); pragma Assert (Get_Id (M) = Id_Memidx); when others => raise Internal_Error; end case; if Is_Reverse then declare Inp : constant Input := Get_Input (M, 0); Sub : constant Instance := Get_Net_Parent (Get_Driver (Inp)); Addr_Inp : constant Input := Get_Input (Sub, 1); Val : Net; begin -- Disconnect the sub, and connect the address directly. Disconnect (Inp); Connect (Inp, Disconnect_And_Get (Addr_Inp)); -- Remove the sub and the constant. Val := Disconnect_And_Get (Get_Input (Sub, 0)); Remove_Instance (Get_Net_Parent (Val)); Remove_Instance (Sub); end; end if; end loop; exit when Done; end; end loop; Free_Instance_Array (Ports); end Maybe_Remap_Address; -- Create a mem_rd/mem_rd_sync from a dyn_extract gate. -- LAST is the last memory port on the chain. -- ADDR is the address (from the dyn_extract). -- VAL is the output of the dyn_extract. -- -- Infere a synchronous read if the dyn_extract is connected to a dff. function Create_ROM_Read_Port (Ctxt : Context_Acc; Last : Net; Addr : Net; Val : Net; Step : Width) return Instance is W : constant Width := Get_Width (Val); Res : Instance; Inp : Input; Iinst : Instance; N : Net; begin Inp := Get_First_Sink (Val); if Get_Next_Sink (Inp) = No_Input then -- There is a single input. Iinst := Get_Input_Parent (Inp); if Get_Id (Iinst) = Id_Dff then -- The output of the dyn_extract is directly connected to a dff. -- So this is a synchronous read without enable. declare Clk_Inp : Input; Clk : Net; En : Net; begin Clk_Inp := Get_Input (Iinst, 0); Clk := Get_Driver (Clk_Inp); Disconnect (Clk_Inp); En := Build_Const_UB32 (Ctxt, 1, 1); Disconnect (Inp); Res := Build_Mem_Rd_Sync (Ctxt, Last, Addr, Clk, En, Step); -- Slice the output. N := Get_Output (Res, 1); N := Build2_Extract (Ctxt, N, 0, W); Redirect_Inputs (Get_Output (Iinst, 0), N); Remove_Instance (Iinst); return Res; end; elsif Get_Id (Iinst) = Id_Mux2 and then Is_Enable_Dff (Inp) then declare Mux_Out : constant Net := Get_Output (Iinst, 0); Mux_En_Inp : constant Input := Get_Input (Iinst, 0); Mux_I0_Inp : constant Input := Get_Input (Iinst, 1); Mux_I1_Inp : constant Input := Get_Input (Iinst, 2); Dff_Din : constant Input := Get_First_Sink (Mux_Out); Dff_Inst : constant Instance := Get_Input_Parent (Dff_Din); Dff_Out : constant Net := Get_Output (Dff_Inst, 0); Clk_Inp : constant Input := Get_Input (Dff_Inst, 0); Clk : constant Net := Get_Driver (Clk_Inp); En : Net; begin En := Get_Driver (Mux_En_Inp); if Dff_Out = Get_Driver (Mux_I1_Inp) then En := Build_Monadic (Ctxt, Id_Not, En); Copy_Location (En, Dff_Inst); end if; Disconnect (Mux_En_Inp); Disconnect (Mux_I0_Inp); Disconnect (Mux_I1_Inp); Disconnect (Dff_Din); Disconnect (Clk_Inp); Remove_Instance (Iinst); Res := Build_Mem_Rd_Sync (Ctxt, Last, Addr, Clk, En, Step); Set_Location (Res, Get_Location (Dff_Inst)); -- Slice the output. N := Get_Output (Res, 1); N := Build2_Extract (Ctxt, N, 0, W); Redirect_Inputs (Dff_Out, N); Remove_Instance (Dff_Inst); return Res; end; end if; end if; -- Replace Dyn_Extract with mem_rd. Res := Build_Mem_Rd (Ctxt, Last, Addr, Step); -- Slice the output. N := Get_Output (Res, 1); N := Build2_Extract (Ctxt, N, 0, W); Redirect_Inputs (Val, N); return Res; end Create_ROM_Read_Port; -- MEM_INST is the memory instance. procedure Replace_ROM_Read_Ports (Ctxt : Context_Acc; Orig : Instance; Mem_Inst : Instance; Step : Width) is Orig_Net : constant Net := Get_Output (Orig, 0); Last : Net; Inp : Input; Next_Inp : Input; Extr_Inst : Instance; Addr_Inp : Input; Addr : Net; Val : Net; Port_Inst : Instance; begin Last := Get_Output (Mem_Inst, 0); -- Convert readers. Inp := Get_First_Sink (Orig_Net); while Inp /= No_Input loop Next_Inp := Get_Next_Sink (Inp); Extr_Inst := Get_Input_Parent (Inp); case Get_Id (Extr_Inst) is when Id_Memory_Init => null; when Id_Dyn_Extract => Disconnect (Inp); -- Check offset if Get_Param_Uns32 (Extr_Inst, 0) /= 0 then raise Internal_Error; end if; -- Convert memidx. Addr_Inp := Get_Input (Extr_Inst, 1); Addr := Get_Driver (Addr_Inp); Disconnect (Addr_Inp); Val := Get_Output (Extr_Inst, 0); Convert_Memidx (Ctxt, Orig, Addr, Step); -- Replace Dyn_Extract with mem_rd. Port_Inst := Create_ROM_Read_Port (Ctxt, Last, Addr, Val, Step); Remove_Instance (Extr_Inst); Last := Get_Output (Port_Inst, 0); when others => raise Internal_Error; end case; Inp := Next_Inp; end loop; -- Close the loop. Connect (Get_Input (Mem_Inst, 0), Last); end Replace_ROM_Read_Ports; -- ORIG (the memory) must be Const. procedure Replace_ROM_Memory (Ctxt : Context_Acc; Orig : Instance; Step : Width) is Orig_Net : constant Net := Get_Output (Orig, 0); Name : constant Sname := New_Internal_Name (Ctxt); Inst : Instance; begin Inst := Build_Memory_Init (Ctxt, Name, Get_Width (Orig_Net), Orig_Net); Replace_ROM_Read_Ports (Ctxt, Orig, Inst, Step); end Replace_ROM_Memory; type Get_Next_Status is ( Status_None, Status_One, Status_Multiple ); -- O is the output of a gate. Returns the gate driven by O, ignoring -- Dyn_Extract or muxes to Dyn_Extract. -- Return No_Instance if there is no output or multiple outputs. procedure Get_Next_Non_Extract (O : Net; Status : out Get_Next_Status; Res : out Instance) is Inp : Input; begin Status := Status_None; Res := No_Instance; -- Scan all the gates driven by the output. Inp := Get_First_Sink (O); while Inp /= No_Input loop declare Pinst : constant Instance := Get_Input_Parent (Inp); This_Next_Inst : Instance; begin This_Next_Inst := No_Instance; case Get_Id (Pinst) is when Id_Dyn_Extract => -- Ignore dyn_extract null; when Id_Mux2 => -- It is OK to have mux2, provided it is connected to -- a dyn_extract. declare Mux_Out : constant Net := Get_Output (Pinst, 0); Sub_Status : Get_Next_Status; Sub_Res : Instance; begin if Mux_Out = O then -- Avoid simple infinite recursion Status := Status_None; Res := No_Instance; return; end if; Get_Next_Non_Extract (Mux_Out, Sub_Status, Sub_Res); -- Expect Dyn_Extract, so no next. if Sub_Status /= Status_None then Status := Status_Multiple; Res := No_Instance; return; end if; end; when others => This_Next_Inst := Pinst; end case; if This_Next_Inst /= No_Instance then if Res /= No_Instance then -- More than one next gate. Status := Status_Multiple; Res := No_Instance; return; end if; Status := Status_One; Res := This_Next_Inst; end if; end; Inp := Get_Next_Sink (Inp); end loop; end Get_Next_Non_Extract; -- Try to reach Id_Signal/Id_Isignal (TODO: Id_Output) from dyn_insert -- gate FIRST_INST. Can only walk through dyn_insert and muxes. -- Return the memory if found. function Walk_From_Insert (First_Inst : Instance) return Instance is Status : Get_Next_Status; Inst : Instance; Next_Inst : Instance; Last : Instance; O : Net; begin -- LAST is the last interesting gate (dyn_insert) which has a -- meaningful location. Last := First_Inst; Inst := First_Inst; loop case Get_Id (Inst) is when Id_Dyn_Insert | Id_Dyn_Insert_En => if Get_Mark_Flag (Inst) then -- Already seen. return No_Instance; end if; Set_Mark_Flag (Inst, True); Last := Inst; O := Get_Output (Inst, 0); when Id_Mux2 | Id_Mux4 => O := Get_Output (Inst, 0); when Id_Dff | Id_Idff | Id_Mdff | Id_Midff => O := Get_Output (Inst, 0); when Id_Isignal | Id_Signal => return Inst; when Id_Mem_Multiport => O := Get_Output (Inst, 0); when others => if Flag_Memory_Verbose then Info_Msg_Synth (+Last, "gate %i cannot be part of a memory", (1 => +Inst)); end if; return No_Instance; end case; -- Next gate. Get_Next_Non_Extract (O, Status, Next_Inst); case Status is when Status_Multiple => -- More than one next gate. if Flag_Memory_Verbose then Info_Msg_Synth (+Last, "gate %i drives several gates", (1 => +Inst)); end if; return No_Instance; when Status_None => if Flag_Memory_Verbose then Info_Msg_Synth (+Last, "gate %i drives no gate", (1 => +Inst)); end if; return No_Instance; when Status_One => Inst := Next_Inst; end case; end loop; end Walk_From_Insert; function Walk_From_Extract (First_Inst : Instance) return Instance is Inst : Instance; Last : Instance; begin -- LAST is the last interesting gate (dyn_extract) which has a -- meaningful location. Last := First_Inst; Inst := First_Inst; loop case Get_Id (Inst) is when Id_Dyn_Extract => if Get_Mark_Flag (Inst) then -- Already seen. return No_Instance; end if; Set_Mark_Flag (Inst, True); Last := Inst; Inst := Get_Input_Instance (Inst, 0); when Id_Isignal | Id_Signal | Id_Const_Bit | Id_Const_Log => return Inst; when others => if Flag_Memory_Verbose then Info_Msg_Synth (+Last, "gate %i cannot be part of a memory", (1 => +Last)); end if; return No_Instance; end case; end loop; end Walk_From_Extract; procedure Unmark_Table (Els : Instance_Tables.Instance) is Inst : Instance; begin for I in Instance_Tables.First .. Instance_Tables.Last (Els) loop Inst := Els.Table (I); Set_Mark_Flag (Inst, False); end loop; end Unmark_Table; -- INSERT is a Dyn_Insert[_En]. Get the next gates until reaching a -- signal. -- Validate that signal SIG is a RAM. It must be a loop of inserts -- and extracts. function Validate_RAM_Simple (Insert : Instance) return Instance is Inst : Instance; N : Net; Inp : Input; begin -- For each gate of the chain, starting from LAST and going forward -- until the signal. N := Get_Output (Insert, 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 | Id_Dyn_Insert | Id_Mem_Multiport | Id_Dff | Id_Idff => if N /= No_Net then -- There must be only one such gate per stage. return No_Instance; end if; N := Get_Output (Inst, 0); when Id_Mdff | Id_Midff => if Inp = Get_Input (Inst, 1) then -- Data. if N /= No_Net then -- There must be only one such gate per stage. return No_Instance; end if; N := Get_Output (Inst, 0); else -- Ignore. null; end if; when Id_Dyn_Extract => null; when Id_Isignal | Id_Signal => return Inst; when others => return No_Instance; end case; Inp := Get_Next_Sink (Inp); end loop; end loop; return No_Instance; end Validate_RAM_Simple; -- Validate that signal SIG is a RAM. It must be a loop of inserts -- and extracts. function Validate_RAM_Multiple (Sig : Instance) return Boolean is Ok : Boolean; Inst : Instance; N : Net; Inp : Input; begin Ok := False; N := Get_Output (Sig, 0); Inp := Get_First_Sink (N); -- For multiple ports, there can be parallel pathes. while Inp /= No_Input loop Inst := Get_Input_Parent (Inp); case Get_Id (Inst) is when Id_Dyn_Insert_En | Id_Dyn_Insert => -- Look. if Validate_RAM_Simple (Inst) /= Sig then return False; end if; Ok := True; when Id_Dyn_Extract => null; when others => return False; end case; Inp := Get_Next_Sink (Inp); end loop; -- Need at least one dyn_insert. return Ok; end Validate_RAM_Multiple; -- Test if V is part of the conjunction CONJ generated by mux2 controls. function In_Conjunction (Conj : Net; V : Net; Negate : Boolean) return Boolean is Inst : Instance; N : Net; begin -- Simple case (but important for the memories) if V = Conj then return (not Negate); end if; N := Conj; Inst := Get_Net_Parent (N); loop Inst := Get_Net_Parent (N); if Get_Id (Inst) /= Id_And then return (N = V) xor Negate; end if; -- Inst is AND2. if Get_Input_Net (Inst, 0) = V then return (not Negate); end if; N := Get_Input_Net (Inst, 1); end loop; end In_Conjunction; -- Subroutine of Reduce_Extract_Muxes. -- MUX is a mux2 that is removed if possible. procedure Reduce_Extract_Muxes_Mux2 (Mux : Instance; Port : Port_Idx) is pragma Assert (Get_Id (Mux) = Id_Mux2); Sel : constant Net := Get_Input_Net (Mux, 0); Val : constant Net := Get_Input_Net (Mux, 1 + Port); Old : constant Net := Get_Input_Net (Mux, 1 + (1 - Port)); First_Parent, Last_Parent : Instance; P : Instance; N : Net; begin -- Search the parent. First_Parent := Get_Net_Parent (Val); P := First_Parent; loop if Get_Id (P) /= Id_Dyn_Insert_En then if Flag_Memory_Verbose then Info_Msg_Synth (+Mux, "mux %i before extract is not a bypass", (1 => +Mux)); end if; return; end if; -- Get the MEM input. N := Get_Input_Net (P, 0); exit when N = Old; P := Get_Net_Parent (N); end loop; Last_Parent := P; -- Check not SEL (resp. SEL) implies disable for all dyn_insert_en -- parents. P := First_Parent; loop -- Get the enable of Dyn_Insert_En parent. N := Get_Input_Net (P, 3); if not In_Conjunction (N, Sel, Port = 0) then if Flag_Memory_Verbose then Info_Msg_Synth (+Mux, "mux %i before extract is required", (1 => +Mux)); end if; return; end if; exit when P = Last_Parent; P := Get_Net_Parent (Get_Input_Net (P, 0)); end loop; -- So Mux2 is not required. Disconnect (Get_Input (Mux, 0)); Disconnect (Get_Input (Mux, 1)); Disconnect (Get_Input (Mux, 2)); Redirect_Inputs (Get_Output (Mux, 0), Val); Remove_Instance (Mux); end Reduce_Extract_Muxes_Mux2; -- SIG is a signal/isignal at the start of a memory, which consists of -- one or more chain of Dyn_Insert. Dyn_Extract are also allowed on this -- chain. It is also possible to have Mux2 before Dyn_Extract because of -- enable signals. -- Try to remove these mux2. -- * They should be between the output of a dyn_insert and the input of -- a dyn_extract -- * The other input of the mux2 must be a parent of the dyn_insert input -- (in the chain of dyn_insert). -- * All the dyn_insert until the parent must be disabled when the mux2 is -- disabled. procedure Reduce_Extract_Muxes (Sig : Instance) is N : Net; Inp : Input; Next_Inp : Input; Inst : Instance; begin N := Get_Output (Sig, 0); Inp := Get_First_Sink (N); while Inp /= No_Input loop -- INP can be removed, so get the next input now. Next_Inp := Get_Next_Sink (Inp); Inst := Get_Input_Parent (Inp); case Get_Id (Inst) is when Id_Dyn_Insert | Id_Dyn_Insert_En => -- Recurse on it. Reduce_Extract_Muxes (Inst); Next_Inp := Get_Next_Sink (Inp); when Id_Mux2 => if Inp = Get_Input (Inst, 1) then -- Selected when Sel = 0 Reduce_Extract_Muxes_Mux2 (Inst, 0); elsif Inp = Get_Input (Inst, 2) then -- Selected when Sel = 1 Reduce_Extract_Muxes_Mux2 (Inst, 1); else raise Internal_Error; end if; when Id_Isignal | Id_Signal | Id_Mem_Multiport => -- Stop here: do not recurse. null; when Id_Dyn_Extract => -- Ignore. null; when others => null; end case; Inp := Next_Inp; end loop; end Reduce_Extract_Muxes; type Off_Array is array (Int32 range <>) of Uns32; type Off_Array_Acc is access Off_Array; procedure Free_Off_Array is new Ada.Unchecked_Deallocation (Off_Array, Off_Array_Acc); function Off_Array_Search (Arr : Off_Array; Off : Uns32) return Int32 is begin for I in Arr'Range loop if Arr (I) = Off then return I; end if; end loop; raise Internal_Error; end Off_Array_Search; procedure Off_Array_To_Idx (Arr: Off_Array; Off : Uns32; Wd : Uns32; Idx : out Int32; Len : out Int32) is Idx2 : Int32; begin Idx := Off_Array_Search (Arr, Off); Idx2 := Off_Array_Search (Arr (Idx + 1 .. Arr'Last), Off + Wd); Len := Idx2 - Idx; end Off_Array_To_Idx; type Copy_Mode_Type is (Copy_Mode_Bit, Copy_Mode_Val, Copy_Mode_Zx); procedure Copy_Const_Content (Src : Instance; Src_Off : Width; Src_Wd : Width; Dst : Instance; Dst_Wd : Width; Depth : Uns32; Mode : Copy_Mode_Type) is function Off_To_Param (Off : Uns32) return Param_Idx is Res : constant Param_Idx := Param_Idx (Off / 32); begin case Mode is when Copy_Mode_Bit => return Res; when Copy_Mode_Val => return Res * 2; when Copy_Mode_Zx => return Res * 2 + 1; end case; end Off_To_Param; Boff : Uns32; Nbits : Uns32; Word_Idx : Param_Idx; Word_Off : Uns32; Soff : Uns32; Slen : Uns32; Sval : Uns32; Doff : Uns32; Dlen : Uns32; Dval : Uns32; begin Boff := Src_Off; Doff := 0; for I in 0 .. Depth - 1 loop Nbits := Dst_Wd; Soff := Boff; while Nbits > 0 loop -- Try to read as much as possible. Word_Idx := Off_To_Param (Soff); Word_Off := Soff mod 32; Slen := 32 - Word_Off; if Slen > Nbits then Slen := Nbits; end if; Sval := Get_Param_Uns32 (Src, Word_Idx); -- Reframe (put at bit 0, mask extra bits). Sval := Shift_Right (Sval, Natural (Word_Off)); Sval := Sval and Shift_Right (16#ffff_ffff#, Natural (32 - Slen)); Soff := Soff + Slen; Nbits := Nbits - Slen; -- Store. while Slen > 0 loop Word_Idx := Off_To_Param (Doff); Word_Off := Doff mod 32; Dlen := 32 - Word_Off; if Dlen > Slen then Dlen := Slen; end if; Dval := Sval and Shift_Right (16#ffff_ffff#, Natural (32 - Dlen)); Dval := Shift_Left (Dval, Natural (Word_Off)); Dval := Dval or Get_Param_Uns32 (Dst, Word_Idx); Set_Param_Uns32 (Dst, Word_Idx, Dval); Sval := Shift_Right (Sval, Natural (Dlen)); Slen := Slen - Dlen; Doff := Doff + Dlen; end loop; end loop; Boff := Boff + Src_Wd; end loop; end Copy_Const_Content; -- From constant net CST (used to initialize a memory), extract DEPTH sub -- words (bits OFF:OFF + WD - 1). -- Used when memories are split. function Extract_Sub_Constant (Ctxt : Context_Acc; Cst : Instance; Cst_Wd : Uns32; Off : Uns32; Wd : Uns32; Depth : Uns32) return Net is pragma Assert (Depth /= 0); Mem_Wd : constant Width := Wd * Depth; Res : Instance; begin case Get_Id (Cst) is when Id_Const_Bit => Res := Build_Const_Bit (Ctxt, Mem_Wd); Copy_Const_Content (Cst, Off, Cst_Wd, Res, Wd, Depth, Copy_Mode_Bit); return Get_Output (Res, 0); when Id_Const_Log => Res := Build_Const_Log (Ctxt, Mem_Wd); Copy_Const_Content (Cst, Off, Cst_Wd, Res, Wd, Depth, Copy_Mode_Val); Copy_Const_Content (Cst, Off, Cst_Wd, Res, Wd, Depth, Copy_Mode_Zx); return Get_Output (Res, 0); when Id_Const_UB32 => declare N : Net; begin N := Build_Const_UB32 (Ctxt, 0, Mem_Wd); -- Optimize: no need to copy if the value is 0. if Get_Param_Uns32 (Cst, 0) /= 0 then Res := Get_Net_Parent (N); Copy_Const_Content (Cst, Off, Cst_Wd, Res, Wd, Depth, Copy_Mode_Bit); end if; return N; end; when Id_Const_UL32 => declare N : Net; begin N := Build_Const_UL32 (Ctxt, 0, 0, Mem_Wd); -- Optimize: no need to copy if the value is 0. Res := Get_Net_Parent (N); Copy_Const_Content (Cst, Off, Cst_Wd, Res, Wd, Depth, Copy_Mode_Val); Copy_Const_Content (Cst, Off, Cst_Wd, Res, Wd, Depth, Copy_Mode_Zx); return N; end; when Id_Const_X => return Build_Const_X (Ctxt, Mem_Wd); when others => raise Internal_Error; end case; end Extract_Sub_Constant; -- Physical dimension of the memory. type Mem_Dim_Type is record Data_Wd : Width; Depth : Uns32; -- Number of dimensions. Dim : Natural; end record; -- Subroutine of Convert_To_Memory. -- -- Compute the number of ports (dyn_extract and dyn_insert) and the width -- of the memory. Just walk all the gates. procedure Compute_Ports_And_Dim (Sig : Instance; Nbr_Ports : out Int32; Dim : out Mem_Dim_Type) is type Ports_And_Dim_Data is record Nbr_Ports : Int32; Dim : Mem_Dim_Type; Sig : Instance; end record; procedure Ports_And_Dim_Cb (Dyn_Inst : Instance; Data : in out Ports_And_Dim_Data; Fail : out Boolean) is Res : Mem_Dim_Type; Inst : Instance; Idx : Instance; begin Fail := False; case Get_Id (Dyn_Inst) is when Id_Dyn_Extract => Inst := Get_Input_Instance (Dyn_Inst, 1); when Id_Dyn_Insert | Id_Dyn_Insert_En => Inst := Get_Input_Instance (Dyn_Inst, 2); when others => raise Internal_Error; end case; Data.Nbr_Ports := Data.Nbr_Ports + 1; -- Extract the dim (equivalent to data width) of a dyn_insert or -- dyn_extract address. This is either a memidx or an addidx gate. Res := (Data_Wd => 0, Depth => 1, Dim => 0); loop case Get_Id (Inst) is when Id_Addidx => -- Handle the memidx, ... Idx := Get_Input_Instance (Inst, 0); -- .. and continue with the chain. Inst := Get_Input_Instance (Inst, 1); when Id_Memidx => -- Just handle the memidx. Idx := Inst; Inst := No_Instance; when others => raise Internal_Error; end case; Res.Dim := Res.Dim + 1; Res.Data_Wd := Get_Param_Uns32 (Idx, 0); Res.Depth := Res.Depth * (Get_Param_Uns32 (Idx, 1) + 1); exit when Inst = No_Instance; end loop; if Data.Nbr_Ports = 1 then Data.Dim := Res; else -- TODO: handle different width and depth. if Res.Data_Wd /= Data.Dim.Data_Wd then Info_Msg_Synth (+Data.Sig, "memory %n uses different widths", (1 => +Data.Sig)); Data.Nbr_Ports := 0; Fail := True; elsif Res.Depth /= Data.Dim.Depth then Info_Msg_Synth (+Data.Sig, "memory %n uses different depth", (1 => +Data.Sig)); Data.Nbr_Ports := 0; Fail := True; end if; end if; end Ports_And_Dim_Cb; procedure Ports_And_Dim_Foreach_Port is new Foreach_Port (Data_Type => Ports_And_Dim_Data, Cb => Ports_And_Dim_Cb); Data : Ports_And_Dim_Data; begin Data := (Nbr_Ports => 0, Dim => (Data_Wd => 0, Depth => 0, Dim => 0), Sig => Sig); Ports_And_Dim_Foreach_Port (Sig, Data); Nbr_Ports := Data.Nbr_Ports; Dim := Data.Dim; end Compute_Ports_And_Dim; -- Subroutine of Convert_To_Memory. -- -- Extract offsets/width of each port. procedure Extract_Ports_Offsets (Sig : Instance; Offs : Off_Array_Acc; Nbr_Offs : out Int32) is type Ports_Offsets_Data is record Offs : Off_Array_Acc; Nbr_Offs : Int32; end record; procedure Ports_Offsets_Cb (Inst : Instance; Data : in out Ports_Offsets_Data; Fail : out Boolean) is Off : Uns32; Wd : Uns32; Ow : Off_Array (1 .. 2); begin case Get_Id (Inst) is when Id_Dyn_Extract => Off := Get_Param_Uns32 (Inst, 0); Wd := Get_Width (Get_Output (Inst, 0)); when Id_Dyn_Insert_En | Id_Dyn_Insert => Off := Get_Param_Uns32 (Inst, 0); Wd := Get_Width (Get_Input_Net (Inst, 1)); when others => raise Internal_Error; end case; Ow := (Off, Off + Wd); if Data.Nbr_Offs = 0 or else Ow /= Data.Offs (1 .. 2) then Data.Nbr_Offs := Data.Nbr_Offs + 2; Data.Offs (Data.Nbr_Offs -1 .. Data.Nbr_Offs) := Ow; end if; Fail := False; end Ports_Offsets_Cb; procedure Ports_Offsets_Foreach_Port is new Foreach_Port (Data_Type => Ports_Offsets_Data, Cb => Ports_Offsets_Cb); Data : Ports_Offsets_Data; begin Data := (Offs => Offs, Nbr_Offs => 0); Ports_Offsets_Foreach_Port (Sig, Data); Nbr_Offs := Data.Nbr_Offs; end Extract_Ports_Offsets; -- IN_INST is the Dyn_Extract gate. procedure Convert_RAM_Read_Port (Ctxt : Context_Acc; In_Inst : Instance; Mem_Sz : Uns32; Mem_W : Width; Offs : Off_Array_Acc; Tails : Net_Array_Acc; Outs : Net_Array_Acc) is Off : constant Uns32 := Get_Param_Uns32 (In_Inst, 0); Wd : constant Width := Get_Width (Get_Output (In_Inst, 0)); Idx : Int32; Len : Int32; Addr : Net; Rd_Inst : Instance; Rd : Net; Inp2 : Input; En : Net; Clk : Net; Last_Inst : Instance; begin -- Find the corresponding memory/ies for the dyn_extract. Off_Array_To_Idx (Offs.all, Off, Wd, Idx, Len); Inp2 := Get_Input (In_Inst, 1); Addr := Get_Driver (Inp2); Disconnect (Inp2); -- Build the address net. Convert_Memidx (Ctxt, Mem_Sz, Addr, Mem_W); -- Optimize the network. Maybe_Swap_Concat_Mux_Dff (Ctxt, In_Inst); Maybe_Swap_Mux_Concat_Dff (Ctxt, In_Inst); Extract_Extract_Dff (Ctxt, In_Inst, Last_Inst, Clk, En); if Clk /= No_Net and then En = No_Net then En := Build_Const_UB32 (Ctxt, 1, 1); end if; -- iterate to build mem_rd/mem_rd_sync for I in Idx .. Idx + Len - 1 loop if Clk /= No_Net then Rd_Inst := Build_Mem_Rd_Sync (Ctxt, Tails (I), Addr, Clk, En, Offs (Idx + 1) - Offs (Idx)); else Rd_Inst := Build_Mem_Rd (Ctxt, Tails (I), Addr, Offs (Idx + 1) - Offs (Idx)); end if; Tails (I) := Get_Output (Rd_Inst, 0); Outs (I) := Get_Output (Rd_Inst, 1); end loop; Rd := Build2_Concat (Ctxt, Outs (Idx .. Idx + Len - 1)); Redirect_Inputs (Get_Output (Last_Inst, 0), Rd); if Last_Inst /= In_Inst then Remove_Instance (Last_Inst); end if; end Convert_RAM_Read_Port; -- Subroutine of Convert_To_Memory. -- -- Convert dyn_insert/dyn_extract to memory write/read ports. -- SIG is the isignal/signal gate. -- TAILS is the output of memories (so the next value to be read). -- OUTS is a temporary array. procedure Create_RAM_Ports (Ctxt : Context_Acc; Sig : Instance; Mem_Sz : Uns32; Mem_W : Width; Offs : Off_Array_Acc; Tails : Net_Array_Acc; Outs : Net_Array_Acc; Ports : Instance_Array_Acc) is Inst, Inst2 : Instance; Inp, Inp2 : Input; N_Inp, N_Inp2 : Input; N_Inst : Instance; In_Inst : Instance; N_Ports : Nat32; begin -- Start from the end. -- First: the read ports at the end. Inp2 := Get_First_Sink (Get_Output (Sig, 0)); while Inp2 /= No_Input loop N_Inp2 := Get_Next_Sink (Inp2); Inst2 := Get_Input_Parent (Inp2); case Get_Id (Inst2) is when Id_Dyn_Extract => Convert_RAM_Read_Port (Ctxt, Inst2, Mem_Sz, Mem_W, Offs, Tails, Outs); Disconnect (Get_Input (Inst2, 0)); Remove_Instance (Inst2); when Id_Dyn_Insert_En | Id_Dyn_Insert => null; when others => raise Internal_Error; end case; Inp2 := N_Inp2; end loop; -- Second, the chains. Inp2 := Get_First_Sink (Get_Output (Sig, 0)); N_Ports := 0; while Inp2 /= No_Input loop N_Inp2 := Get_Next_Sink (Inp2); Inst2 := Get_Input_Parent (Inp2); -- Do the real work: transform gates to ports. Disconnect (Get_Input (Inst2, 0)); Inst := Inst2; loop -- Handle Inst. If the output is connected to a write port, -- add it (after the read ports). case Get_Id (Inst) is when Id_Dyn_Insert_En | Id_Dyn_Insert => declare Off : constant Uns32 := Get_Param_Uns32 (Inst, 0); Wd : constant Width := Get_Width (Get_Input_Net (Inst, 1)); Idx : Int32; Len : Int32; Addr : Net; Wr_Inst : Instance; Inp2 : Input; Dat : Net; En : 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); if Get_Id (Inst) = Id_Dyn_Insert_En then Inp2 := Get_Input (Inst, 3); En := Get_Driver (Inp2); Disconnect (Inp2); else En := No_Net; end if; Inp2 := Get_Input (Inst, 1); Dat := Get_Driver (Inp2); for I in Idx .. Idx + Len - 1 loop Wr_Inst := Build_Mem_Wr_Sync (Ctxt, Tails (I), Addr, No_Net, En, Build2_Extract (Ctxt, Dat, Offs (I) - Offs (Idx), Offs (I + 1) - Offs (I))); -- Keep instance to add clock. N_Ports := N_Ports + 1; Ports (N_Ports) := Wr_Inst; Tails (I) := Get_Output (Wr_Inst, 0); end loop; Disconnect (Inp2); end; when Id_Dff | Id_Idff | Id_Mdff | Id_Midff => -- Extract clock. declare En : Net; Clk : Net; begin Inp2 := Get_Input (Inst, 0); Inference.Extract_Clock (Ctxt, Get_Driver (Inp2), Clk, En); Disconnect (Inp2); -- Assign clock. for I in Ports'First .. N_Ports loop declare P : constant Instance := Ports (I); En_Inp : constant Input := Get_Input (P, 3); Mem_En : Net; begin Connect (Get_Input (P, 2), Clk); Mem_En := Get_Driver (En_Inp); if Mem_En /= No_Net then Disconnect (En_Inp); if En /= No_Net then Mem_En := Build_Dyadic (Ctxt, Id_And, Mem_En, En); Copy_Location (Mem_En, Inst); end if; else if En = No_Net then Mem_En := Build_Const_UB32 (Ctxt, 1, 1); else Mem_En := En; end if; end if; Connect (En_Inp, Mem_En); end; end loop; N_Ports := 0; end; when Id_Signal | Id_Isignal => null; when others => raise Internal_Error; end case; -- Check gates connected to the output. -- First the read ports (dyn_extract), and also find the next -- gate in the loop. N_Inst := No_Instance; Inp := Get_First_Sink (Get_Output (Inst, 0)); while Inp /= No_Input loop In_Inst := Get_Input_Parent (Inp); N_Inp := Get_Next_Sink (Inp); case Get_Id (In_Inst) is when Id_Dyn_Extract => Convert_RAM_Read_Port (Ctxt, In_Inst, Mem_Sz, Mem_W, Offs, Tails, Outs); pragma Assert (Inp = Get_Input (In_Inst, 0)); Disconnect (Inp); Remove_Instance (In_Inst); when Id_Dyn_Insert_En | Id_Dyn_Insert | Id_Signal | Id_Isignal => pragma Assert (Inp = Get_Input (In_Inst, 0)); Disconnect (Inp); -- This is the next instance (and there must be only -- one next instance). pragma Assert (N_Inst = No_Instance); N_Inst := In_Inst; when Id_Mem_Multiport => Disconnect (Inp); pragma Assert (N_Inst = No_Instance); N_Inst := In_Inst; when Id_Dff | Id_Idff => Disconnect (Inp); -- Disconnect outputs going to mdff.els declare Dout : constant Net := Get_Output (In_Inst, 0); Inp2, N_Inp2 : Input; Inp2_P : Instance; begin Inp2 := Get_First_Sink (Dout); while Inp2 /= No_Input loop N_Inp2 := Get_Next_Sink (Inp2); Inp2_P := Get_Input_Parent (Inp2); if (Get_Id (Inp2_P) = Id_Mdff or else Get_Id (Inp2_P) = Id_Midff) and then Inp2 = Get_Input (Inp2_P, 2) then Disconnect (Inp2); end if; Inp2 := N_Inp2; end loop; end; pragma Assert (N_Inst = No_Instance); N_Inst := In_Inst; when Id_Mdff | Id_Midff => if Inp = Get_Input (In_Inst, 1) then Disconnect (Inp); pragma Assert (N_Inst = No_Instance); N_Inst := In_Inst; end if; when others => raise Internal_Error; end case; Inp := N_Inp; end loop; -- Remove INST. case Get_Id (Inst) is when Id_Dyn_Insert_En | Id_Dyn_Insert | Id_Dff | Id_Mdff => Remove_Instance (Inst); when Id_Midff => -- Foget initial value (the memory initial value is -- extracted from the isignal). Disconnect (Get_Input (Inst, 3)); Remove_Instance (Inst); when Id_Idff => -- Foget initial value (the memory initial value is -- extracted from the isignal). Disconnect (Get_Input (Inst, 2)); Remove_Instance (Inst); when Id_Signal | Id_Isignal => null; when others => raise Internal_Error; end case; Inst := N_Inst; case Get_Id (Inst) is when Id_Signal | Id_Isignal | Id_Mem_Multiport => exit; when others => null; end case; end loop; Inp2 := N_Inp2; end loop; end Create_RAM_Ports; -- Return True iff the initial value of SIG is uniform (same value for -- all bits). function Is_Simple_Init (Sig : Instance) return Boolean is pragma Assert (Get_Id (Sig) = Id_Isignal); Cst : constant Instance := Get_Input_Instance (Sig, 1); begin case Get_Id (Cst) is when Id_Const_0 | Id_Const_X => return True; when Id_Const_UB32 => return Get_Param_Uns32 (Cst, 0) = 0; when others => return False; end case; end Is_Simple_Init; -- SIG is the signal/isignal. procedure Convert_To_Memory (Ctxt : Context_Acc; Sig : Instance) is -- Size of RAM (in bits). Mem_Sz : constant Uns32 := Get_Width (Get_Output (Sig, 0)); Sig_Name : constant Sname := Get_Instance_Name (Sig); Dim : Mem_Dim_Type; -- Width of the RAM, computed from the step of memidx. -- Width is the length of the data bus. Mem_W : Width; -- Number of elements of the memory. -- Sz = W * Depth. Mem_Depth : Uns32; Nbr_Ports : Int32; Inst : Instance; Name : Sname; -- Table of offsets. -- The same RAM can be partially read or written: not all the bits of -- the data bus are read or written. The RAM is split in several -- sub-rams which are fully read/written. -- This table will contain the offset of each sub-rams. Offs : Off_Array_Acc; Nbr_Offs : Int32; Heads : Instance_Array_Acc; Tails : Net_Array_Acc; Outs : Net_Array_Acc; Ports : Instance_Array_Acc; begin -- 1. Walk to count number of insert/extract instances + extract width Nbr_Ports := 0; Mem_W := 0; Inst := Sig; Compute_Ports_And_Dim (Sig, Nbr_Ports, Dim); if Nbr_Ports = 0 then return; end if; Mem_W := Dim.Data_Wd; if Mem_W = 0 then -- No ports ? raise Internal_Error; end if; Mem_Depth := Mem_Sz / Mem_W; Info_Msg_Synth (+Sig, "found RAM %n, width: %v bits, depth: %v", (1 => +Sig, 2 => +Mem_W, 3 => +Mem_Depth)); -- Change the address (convert 'to' direction to 'downto'), to simplify -- the logic. if Get_Id (Sig) = Id_Signal or else (Get_Id (Sig) = Id_Isignal and then Is_Simple_Init (Sig)) then Maybe_Remap_Address (Ctxt, Sig, Nbr_Ports); end if; -- 2. Walk to extract offsets/width -- NOTE: ideally, there are two kinds of offsets: -- * offsets within the width: when the data is a struct -- * offsets larger than the size: multiple memories, which may have -- different sizes. Offs := new Off_Array (1 .. 2 * Nbr_Ports); Extract_Ports_Offsets (Sig, Offs, Nbr_Offs); -- 2.1 Sort the offsets. declare function Lt (Op1, Op2 : Natural) return Boolean is begin return Offs (Nat32 (Op1)) < Offs (Nat32 (Op2)); end Lt; procedure Swap (From : Natural; To : Natural) is T : Uns32; begin T := Offs (Nat32 (From)); Offs (Nat32 (From)) := Offs (Nat32 (To)); Offs (Nat32 (To)) := T; end Swap; procedure Heap_Sort is new Grt.Algos.Heap_Sort (Lt => Lt, Swap => Swap); begin Heap_Sort (Natural (Nbr_Offs)); end; -- 2.2 Remove duplicates. declare P : Nat32; begin P := 1; for I in 2 .. Nbr_Offs loop if Offs (I) /= Offs (P) then P := P + 1; if P /= I then Offs (P) := Offs (I); end if; end if; end loop; Nbr_Offs := P; end; if Offs (Nbr_Offs) < Mem_W then -- Be sure the whole data width is covered. -- FIXME: simply discard unused data bits ? Nbr_Offs := Nbr_Offs + 1; Offs (Nbr_Offs) := Mem_W; end if; -- 3. Create array of instances -- HEADS contains the memory instance. -- TAILS contain the last link to the ports chain. -- OUTS is a temporary. Heads := new Instance_Array (1 .. Nbr_Offs - 1); Tails := new Net_Array (1 .. Nbr_Offs - 1); Outs := new Net_Array (1 .. Nbr_Offs - 1); Ports := new Instance_Array (1 .. Nbr_Ports * Nbr_Offs); -- 4. Create Memory/Memory_Init from signal/isignal. for I in 1 .. Nbr_Offs - 1 loop -- Reuse signal name for the memory name. if Nbr_Offs = 2 then Name := Sig_Name; else Name := New_Sname_Version (Uns32 (I), Sig_Name); end if; declare Data_Wd : constant Width := Offs (I + 1) - Offs (I); Mem_Wd : constant Width := Data_Wd * Mem_Depth; begin case Get_Id (Sig) is when Id_Isignal => Heads (I) := Build_Memory_Init (Ctxt, Name, Mem_Wd, Extract_Sub_Constant (Ctxt, Get_Input_Instance (Sig, 1), Mem_W, Offs (I), Data_Wd, Mem_Depth)); when Id_Signal => Heads (I) := Build_Memory (Ctxt, Name, Mem_Wd); when others => raise Internal_Error; end case; Copy_Instance_Attributes (Heads (I), Sig); Tails (I) := Get_Output (Heads (I), 0); end; end loop; -- 5. For each part of the data, create memory ports Create_RAM_Ports (Ctxt, Sig, Mem_Sz, Mem_W, Offs, Tails, Outs, Ports); -- Close loops. for I in Heads'Range loop Connect (Get_Input (Heads (I), 0), Tails (I)); end loop; -- Finish to remove the signal/isignal. case Get_Id (Inst) is when Id_Isignal => Disconnect (Get_Input (Inst, 1)); when Id_Signal => null; when others => raise Internal_Error; end case; declare Inst2 : Instance; Inp2 : Input; N2 : Net; begin -- The multiport. Inst2 := Inst; Inp2 := Get_Input (Inst2, 0); loop N2 := Get_Driver (Inp2); if N2 /= No_Net then Disconnect (Inp2); Remove_Instance (Inst2); else Remove_Instance (Inst2); exit; end if; Inst2 := Get_Net_Parent (N2); pragma Assert (Get_Id (Inst2) = Id_Mem_Multiport); pragma Assert (Get_Driver (Get_Input (Inst2, 0)) = No_Net); Inp2 := Get_Input (Inst2, 1); end loop; end; -- 6. Cleanup. Free_Off_Array (Offs); Free_Instance_Array (Heads); Free_Net_Array (Tails); Free_Net_Array (Outs); Free_Instance_Array (Ports); end Convert_To_Memory; function Is_Const_Input (Inst : Instance) return Boolean is begin case Get_Id (Inst) is when Constant_Module_Id => return True; when Id_Signal | Id_Isignal => declare Inp : constant Net := Get_Input_Net (Inst, 0); begin if Inp = No_Net then return False; else return Is_Const_Input (Get_Net_Parent (Inp)); end if; end; when others => -- FIXME: handle other consts ? return False; end case; end Is_Const_Input; -- The main entry point. procedure Extract_Memories (Ctxt : Context_Acc; M : Module) is Dyns : Instance_Tables.Instance; Mems : Instance_Tables.Instance; Inst : Instance; begin Instance_Tables.Init (Dyns, 16); -- Gather all Dyn_Insert/Dyn_Extract. Inst := Get_First_Instance (M); while Inst /= No_Instance loop -- Walk all the instances of M: case Get_Id (Inst) is when Id_Dyn_Insert_En | Id_Dyn_Insert | Id_Dyn_Extract => Instance_Tables.Append (Dyns, Inst); pragma Assert (Get_Mark_Flag (Inst) = False); when others => null; end case; Inst := Get_Next_Instance (Inst); end loop; if Instance_Tables.Last (Dyns) < Instance_Tables.First then -- No dyn gates so no memory. Early return. Instance_Tables.Free (Dyns); return; end if; Instance_Tables.Init (Mems, 16); -- Extract memories from dyn gates: -- get the isignal/signal/const gate at the origin of the dyn gate. for I in Instance_Tables.First .. Instance_Tables.Last (Dyns) loop Inst := Dyns.Table (I); if not Get_Mark_Flag (Inst) then case Get_Id (Inst) is when Id_Dyn_Insert | Id_Dyn_Insert_En => Inst := Walk_From_Insert (Inst); when Id_Dyn_Extract => Inst := Walk_From_Extract (Inst); when others => raise Internal_Error; end case; if Inst /= No_Instance and then not Get_Mark_Flag (Inst) then -- New (candidate) memory ! Set_Mark_Flag (Inst, True); Instance_Tables.Append (Mems, Inst); end if; end if; end loop; -- Unmark dyn gates. Unmark_Table (Dyns); Instance_Tables.Free (Dyns); -- Unmark memory gates. Unmark_Table (Mems); -- Convert to RAM or ROM. for I in Instance_Tables.First .. Instance_Tables.Last (Mems) loop -- INST is the memorizing instance, ie isignal/signal. Inst := Mems.Table (I); declare Data_W : Width; Size : Width; begin case Get_Id (Inst) is when Id_Isignal | Id_Signal | Id_Const_Bit | Id_Const_Log => null; when others => raise Internal_Error; end case; if Is_Const_Input (Inst) then Check_Memory_Read_Ports (Inst, Data_W, Size); if Data_W /= 0 then Info_Msg_Synth (+Inst, "found ROM %n, width: %v bits, depth: %v", (1 => +Inst, 2 => +Data_W, 3 => +Size)); Replace_ROM_Memory (Ctxt, Inst, Data_W); end if; else Reduce_Extract_Muxes (Inst); if Validate_RAM_Multiple (Inst) then Convert_To_Memory (Ctxt, Inst); end if; end if; end; end loop; Instance_Tables.Free (Mems); end Extract_Memories; -- Return True iff O is to MUX and any number of Dyn_Extract (possibly -- through mux2). function One_Write_Connection (O : Net; Mux : Instance) return Boolean is Inp : Input; Parent : Instance; begin Inp := Get_First_Sink (O); while Inp /= No_Input loop Parent := Get_Input_Parent (Inp); case Get_Id (Parent) is when Id_Dyn_Extract => null; when Id_Mux2 => if Parent /= Mux then -- Can be a mux for a dyn_extract. declare In2 : Input; begin loop In2 := Get_First_Sink (Get_Output (Parent, 0)); if In2 = No_Input or else Get_Next_Sink (In2) /= No_Input then -- Drives more than one gate. return False; end if; Parent := Get_Input_Parent (In2); case Get_Id (Parent) is when Id_Dyn_Extract => exit; when Id_Mux2 => null; when others => return False; end case; end loop; end; end if; when others => return False; end case; Inp := Get_Next_Sink (Inp); end loop; return True; end One_Write_Connection; procedure Reduce_Muxes_Mux2 (Ctxt : Context_Acc; Clk : Net; Psel : Net; Head : in out Instance; Tail : out Instance); -- Remove the mux2 MUX (by adding enable to dyn_insert). -- Return the new head. procedure Reduce_Muxes (Ctxt : Context_Acc; Clk : Net; Sel : Net; Head_In : Net; Tail_In : Net; Head_Out : out Instance; Tail_Out : out Instance) is Inst : Instance; N : Net; begin -- Reduce Drv until Src. -- Transform dyn_insert to dyn_insert_en by adding SEL, or simply add -- SEL to existing dyn_insert_en. -- RES is the head of the result chain. N := Head_In; Head_Out := No_Instance; while N /= Tail_In loop Inst := Get_Net_Parent (N); case Get_Id (Inst) is when Id_Mux2 => -- Recurse on the mux. Reduce_Muxes_Mux2 (Ctxt, Clk, Sel, Inst, Tail_Out); when Id_Dyn_Insert => -- Transform dyn_insert to dyn_insert_en. declare En : Net; begin if Clk /= No_Net then if Sel /= No_Net then En := Build_Dyadic (Ctxt, Id_And, Clk, Sel); Copy_Location (En, Sel); else En := Clk; end if; else En := Sel; end if; if En /= No_Net then Inst := Add_Enable_To_Dyn_Insert (Ctxt, Inst, En); end if; end; Tail_Out := Inst; when Id_Dyn_Insert_En => -- Simply add SEL to the enable input. declare En_Inp : constant Input := Get_Input (Inst, 3); En : Net; begin En := Get_Driver (En_Inp); Disconnect (En_Inp); if Sel /= No_Net then En := Build_Dyadic (Ctxt, Id_And, En, Sel); Copy_Location (En, Sel); end if; if Clk /= No_Net then En := Build_Dyadic (Ctxt, Id_And, Clk, En); Copy_Location (En, Inst); end if; Connect (En_Inp, En); end; Tail_Out := Inst; when Id_Signal | Id_Isignal => pragma Assert (Tail_In = No_Net); Tail_Out := Inst; exit; when others => raise Internal_Error; end case; -- If this is the head, keep it. if Head_Out = No_Instance then Head_Out := Inst; end if; -- Continue the walk with the next element. N := Get_Input_Net (Tail_Out, 0); end loop; -- For memories described by a single process like this: -- if wen then -- mem (addr) := din; -- end if; -- if rden then -- dout := mem (addr); -- end if; -- the writer has just been reduced, but the reader can also be reduced. -- _ -- _ / |0-----------------\ -- / |1-- dyn_extract ---+----| | | -- dout ---| | | \_|1--- dyn_insert --+--- mem -- \_|0-- dout | | | -- | | wen | -- rden _ | | -- / |1---/ | -- mem ----- isignal -----| | | -- \_|0------------------------------/ -- | -- +clk -- Was just reduced to: -- _ -- / |1-- dyn_extract ---+--- dyn_insert_en --+--- mem -- dout ---| | | | -- \_|0-- dout | | -- | | | -- rden _ | | -- / |1---/ | -- mem ----- isignal -----| | | -- \_|0------------------------/ -- | -- +clk -- Note: Previously, `+clk` and `wen` were fused to the same mux (as an -- optimization), requiring extraction. Now the optimization is not -- performed when a wire is read, thus simplifying the reduction here. end Reduce_Muxes; -- Remove the mux2 HEAD (by adding enable to dyn_insert). -- Return the new head. procedure Reduce_Muxes_Mux2 (Ctxt : Context_Acc; Clk : Net; Psel : Net; Head : in out Instance; Tail : out Instance) is 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); Sel : Net; Drv0 : Net; Drv1 : Net; Drv : Net; Src : Net; Res : Instance; begin Drv0 := Get_Driver (In0); Drv1 := Get_Driver (In1); Sel := Get_Driver (Sel_Inp); -- 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 if One_Write_Connection (Drv0, Mux) and then not Has_One_Connection (Drv1) then Disconnect (In0); Disconnect (In1); Disconnect (Sel_Inp); Drv := Drv0; Src := Drv1; Sel := Build_Monadic (Ctxt, Id_Not, Sel); Copy_Location (Sel, Mux); elsif Has_One_Connection (Drv1) and then not Has_One_Connection (Drv0) then Disconnect (In0); Disconnect (In1); Disconnect (Sel_Inp); Drv := Drv1; Src := Drv0; else -- Not an enable mux. raise Internal_Error; end if; if Psel /= No_Net then Sel := Build_Dyadic (Ctxt, Id_And, Psel, Sel); Copy_Location (Sel, Psel); end if; -- Reduce Drv until Src. -- Transform dyn_insert to dyn_insert_en by adding SEL, or simply add -- SEL to existing dyn_insert_en. -- RES is the head of the result chain. Reduce_Muxes (Ctxt, Clk, Sel, Drv, Src, Res, Tail); Redirect_Inputs (Muxout, Get_Output (Res, 0)); Remove_Instance (Mux); Head := Res; end Reduce_Muxes_Mux2; function Infere_RAM (Ctxt : Context_Acc; Val : Net; Tail : Net; Clk : Net; En : Net) return Net is -- pragma Assert (not Is_Connected (Val)); New_Tail : Instance; Res : Instance; begin -- From VAL, 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. -- Return the new head. Reduce_Muxes (Ctxt, Clk, En, Val, Tail, Res, New_Tail); return Get_Output (Res, 0); end Infere_RAM; 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 -- -- But there can be dyn_extract almost anywhere. Drv0 := Get_Input_Net (Mux, 1); Drv1 := Get_Input_Net (Mux, 2); if One_Write_Connection (Drv0, Mux) and then not One_Write_Connection (Drv1, Mux) then Drv := Drv0; Src := Drv1; elsif One_Write_Connection (Drv1, Mux) and then not One_Write_Connection (Drv0, Mux) 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 | Id_Dyn_Insert_En => -- 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_Dff => -- Skip dff. Inst := Get_Input_Instance (Inst, 1); when Id_Signal | Id_Isignal => return Get_Output (Inst, 0) = Prev_Val; when others => return False; end case; end loop; end Can_Infere_RAM; end Netlists.Memories;