From b3cb6b9c638e9a45afec449a1cf1a5ea4c34756d Mon Sep 17 00:00:00 2001
From: Tristan Gingold <tgingold@free.fr>
Date: Tue, 14 Jan 2020 22:00:47 +0100
Subject: netlists: use a mark and sweep cleanup.
---
src/synth/netlists-cleanup.adb | 119 +++++++++++++++++++++++++++++++++++++++++
src/synth/netlists-cleanup.ads | 4 ++
src/synth/netlists.adb | 1 +
src/synth/synth-insts.adb | 3 +-
4 files changed, 126 insertions(+), 1 deletion(-)
(limited to 'src')
diff --git a/src/synth/netlists-cleanup.adb b/src/synth/netlists-cleanup.adb
index f7342add9..4b4360e7f 100644
--- a/src/synth/netlists-cleanup.adb
+++ b/src/synth/netlists-cleanup.adb
@@ -141,4 +141,123 @@ package body Netlists.Cleanup is
end loop;
end Remove_Output_Gates;
+ procedure Insert_Mark_And_Sweep (Inspect : in out Instance_Tables.Instance;
+ Inst : Instance) is
+ begin
+ if not Get_Mark_Flag (Inst) then
+ Set_Mark_Flag (Inst, True);
+ Instance_Tables.Append (Inspect, Inst);
+ end if;
+ end Insert_Mark_And_Sweep;
+
+ procedure Mark_And_Sweep (M : Module)
+ is
+ use Netlists.Gates;
+ Inspect : Instance_Tables.Instance;
+
+ Inst : Instance;
+ Inp : Input;
+ begin
+ Instance_Tables.Init (Inspect, 64);
+
+ -- 1. Check instances are not marked.
+ -- 1.1 Insert assertion gates.
+ Inst := Get_First_Instance (M);
+ while Inst /= No_Instance loop
+ pragma Assert (Get_Mark_Flag (Inst) = False);
+
+ case Get_Id (Inst) is
+ when Id_Assert
+ | Id_Assume
+ | Id_Cover
+ | Id_Assert_Cover =>
+ Insert_Mark_And_Sweep (Inspect, Inst);
+ when others =>
+ null;
+ end case;
+ Inst := Get_Next_Instance (Inst);
+ end loop;
+
+ -- 1.2 Insert output drivers.
+ -- This corresponds to the input of the self instance.
+ Insert_Mark_And_Sweep (Inspect, Get_Self_Instance (M));
+
+ -- 2. While the table is not empty, extract an element and insert
+ -- all the input drivers.
+ loop
+ declare
+ Idx : Int32;
+ N : Net;
+ begin
+ Idx := Instance_Tables.Last (Inspect);
+ exit when Idx < Instance_Tables.First;
+ Inst := Inspect.Table (Idx);
+ Instance_Tables.Decrement_Last (Inspect);
+
+ for I in 1 .. Get_Nbr_Inputs (Inst) loop
+ N := Get_Input_Net (Inst, I - 1);
+ if N /= No_Net then
+ Insert_Mark_And_Sweep (Inspect, Get_Net_Parent (N));
+ end if;
+ end loop;
+ end;
+ end loop;
+
+ -- 3. Remove unused instances; unmark used instances.
+ Instance_Tables.Free (Inspect);
+ declare
+ Next_Inst : Instance;
+ First_Unused : Instance;
+ Last_Unused : Instance;
+ begin
+ First_Unused := No_Instance;
+
+ Extract_All_Instances (M, Inst);
+ -- But keep the self-instance.
+ pragma Assert (Get_Mark_Flag (Inst));
+ Set_Mark_Flag (Inst, False);
+ Next_Inst := Get_Next_Instance (Inst);
+ Append_Instance (M, Inst);
+ Inst := Next_Inst;
+ while Inst /= No_Instance loop
+ Next_Inst := Get_Next_Instance (Inst);
+ if Get_Mark_Flag (Inst) then
+ -- Instance was marked, keept it.
+ Set_Mark_Flag (Inst, False);
+ Append_Instance (M, Inst);
+ else
+ -- Instance was not marked, disconnect it.
+ for I in 1 .. Get_Nbr_Inputs (Inst) loop
+ Inp := Get_Input (Inst, I - 1);
+ if Get_Driver (Inp) /= No_Net then
+ -- Disconnect the input.
+ Disconnect (Inp);
+ end if;
+ end loop;
+
+ if First_Unused = No_Instance then
+ First_Unused := Inst;
+ else
+ Set_Next_Instance (Last_Unused, Inst);
+ end if;
+ Last_Unused := Inst;
+ end if;
+ Inst := Next_Inst;
+ end loop;
+
+ -- Free unused instances. This must be done at the end so that
+ -- their outputs are disconnected.
+ if First_Unused /= No_Instance then
+ Set_Next_Instance (Last_Unused, No_Instance);
+ loop
+ Inst := First_Unused;
+ exit when Inst = No_Instance;
+ First_Unused := Get_Next_Instance (Inst);
+
+ Free_Instance (Inst);
+ end loop;
+ end if;
+ end;
+ end Mark_And_Sweep;
+
end Netlists.Cleanup;
diff --git a/src/synth/netlists-cleanup.ads b/src/synth/netlists-cleanup.ads
index c4c82addf..bb9679100 100644
--- a/src/synth/netlists-cleanup.ads
+++ b/src/synth/netlists-cleanup.ads
@@ -24,6 +24,10 @@ package Netlists.Cleanup is
-- that are also removed.
procedure Remove_Unconnected_Instances (M : Module);
+ -- Stronger version of Remove_Unconnected_Instances: use a mark and
+ -- sweep algorithm.
+ procedure Mark_And_Sweep (M : Module);
+
-- Remove Id_Output gates.
procedure Remove_Output_Gates (M : Module);
end Netlists.Cleanup;
diff --git a/src/synth/netlists.adb b/src/synth/netlists.adb
index 7760e7629..c7c9edb96 100644
--- a/src/synth/netlists.adb
+++ b/src/synth/netlists.adb
@@ -322,6 +322,7 @@ package body Netlists is
Instances_Table.Table (M_Ent.Last_Instance).Next_Instance := Inst;
end if;
Instances_Table.Table (Inst).Prev_Instance := M_Ent.Last_Instance;
+ Instances_Table.Table (Inst).Next_Instance := No_Instance;
M_Ent.Last_Instance := Inst;
end Append_Instance;
diff --git a/src/synth/synth-insts.adb b/src/synth/synth-insts.adb
index 2703ae74a..c5ed77f4d 100644
--- a/src/synth/synth-insts.adb
+++ b/src/synth/synth-insts.adb
@@ -1403,7 +1403,8 @@ package body Synth.Insts is
-- a correctness point: there might be some unsynthesizable gates, like
-- the one created for 'rising_egde (clk) and not rst'.
if not Synth.Flags.Flag_Debug_Nocleanup then
- Netlists.Cleanup.Remove_Unconnected_Instances (Inst.M);
+ -- Netlists.Cleanup.Remove_Unconnected_Instances (Inst.M);
+ Netlists.Cleanup.Mark_And_Sweep (Inst.M);
Netlists.Cleanup.Remove_Output_Gates (Inst.M);
end if;
--
cgit v1.2.3