1-- Netlist. 2-- Copyright (C) 2017 Tristan Gingold 3-- 4-- This file is part of GHDL. 5-- 6-- This program is free software; you can redistribute it and/or modify 7-- it under the terms of the GNU General Public License as published by 8-- the Free Software Foundation; either version 2 of the License, or 9-- (at your option) any later version. 10-- 11-- This program is distributed in the hope that it will be useful, 12-- but WITHOUT ANY WARRANTY; without even the implied warranty of 13-- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14-- GNU General Public License for more details. 15-- 16-- You should have received a copy of the GNU General Public License 17-- along with this program; if not, write to the Free Software 18-- Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, 19-- MA 02110-1301, USA. 20 21with Types; use Types; 22with Hash; use Hash; 23with Dyn_Maps; 24 25package Netlists is 26 -- Netlists. 27 -- 28 -- A netlist is a graph of gates and nets. This implementation has some 29 -- particularities: 30 -- * the nets are vectors of bits, and a net of one bit is in fact a 31 -- vector of net 1. Vectors only have a width, their bounds are 32 -- from (width - 1 downto 0) or [width-1:0]. 33 -- * there is no separate data structures for nets, so nets are in 34 -- fact the outputs of gates. So there is no standalone nets, a gate 35 -- is needed to have a net. 36 37 -- Names. 38 -- As there are many artificial and hierarchical names in a netlist, names 39 -- are not flat: it is possible to create a new name using an existing one 40 -- without copying the whole prefix. 41 type Sname_Kind is 42 ( 43 -- The name adds a suffix to an existing name. Simple names (without 44 -- prefix) are in this kind, with a null prefix. 45 Sname_User, 46 Sname_Artificial, 47 48 -- Create a new version of an existing prefix. 49 Sname_Version 50 ); 51 pragma Convention (C, Sname_Kind); 52 53 type Sname is private; 54 No_Sname : constant Sname; 55 56 -- Create an Sname. 57 -- There is no unification: these routines always create a new name. There 58 -- is no check that the name already exists, so these routines may create 59 -- a duplicate name. Callers must ensure they create uniq names. 60 function New_Sname_User (Id : Name_Id; Prefix : Sname) return Sname; 61 function New_Sname_Artificial (Id : Name_Id; Prefix : Sname) return Sname; 62 function New_Sname_Version (Ver : Uns32; Prefix : Sname) return Sname; 63 64 -- Read the content of an Sname. 65 function Get_Sname_Kind (Name : Sname) return Sname_Kind; 66 function Get_Sname_Prefix (Name : Sname) return Sname; 67 function Get_Sname_Suffix (Name : Sname) return Name_Id; 68 function Get_Sname_Version (Name : Sname) return Uns32; 69 70 -- Modifies an Sname. 71 procedure Set_Sname_Prefix (Name : Sname; Prefix : Sname); 72 73 -- TODO: procedure to free an Sname. 74 75 -- Module. 76 -- 77 -- A module represent an uninstantiated netlist. It is composed of nets 78 -- and instances. 79 -- 80 -- From the outside, a module has ports (inputs and outputs), and 81 -- optionally parameters. A module must have at least one port. Both 82 -- ports and parameters have names. 83 -- 84 -- From a module, you can get the list of ports, and the list of instances. 85 -- Instances have names. 86 -- 87 -- In a module, there is a special instance (the self one) one that 88 -- represent the ports of the module itself, but with the opposite 89 -- direction. Using this trick, there is no difference between ports of 90 -- instances and ports of the module itself. 91 -- 92 -- In some cases, you also want to read an output port. This is 93 -- not possible in this model, so just add an 'output' gate that 94 -- is a nop but provides a net. 95 -- 96 -- Some modules are predefined and therefore have no inner description. 97 -- These are the well known elementary gates. 98 type Module is private; 99 No_Module : constant Module; 100 101 -- An instance is an instantiated module within a module. It is 102 -- connected. 103 type Instance is private; 104 No_Instance : constant Instance; 105 106 type Instance_Array is array (Int32 range <>) of Instance; 107 108 -- Hash INST (simply return its index). 109 function Hash (Inst : Instance) return Hash_Value_Type; 110 111 -- A net is an output of a gate or a sub-circuit. A net can be connected 112 -- to several inputs. 113 type Net is private; 114 No_Net : constant Net; 115 116 -- So pervasive that it is worth defining this array here. 117 type Net_Array is array (Int32 range <>) of Net; 118 119 type Input is private; 120 No_Input : constant Input; 121 122 -- Witdh of a net, ie number of bits. 123 -- No_Width (value 0) is reserved to mean unknown. This is allowed only to 124 -- describe the width of predefined gates (like and) so that the same 125 -- module can be used for any width. 126 subtype Width is Uns32; 127 No_Width : constant Width := 0; 128 129 type Port_Kind is (Port_In, Port_Out, Port_Inout); 130 131 -- Each module has a numeric identifier that can be used to easily identify 132 -- a module. Gates (and, or, ...) have reserved identifiers. 133 type Module_Id is new Uns32; 134 135 -- Reserved id for no identifier. 136 Id_None : constant Module_Id := 0; 137 138 -- Unused instance: free instance but still linked. 139 Id_Free : constant Module_Id := 1; 140 141 -- Reserved id for a design (top-level module without ports that contains 142 -- other modules). 143 Id_Design : constant Module_Id := 2; 144 145 -- First id for user. 146 Id_User_None : constant Module_Id := 128; 147 Id_User_Parameters : constant Module_Id := 129; 148 Id_User_First : constant Module_Id := Id_User_Parameters + 1; 149 150 -- Port index. Starts at 0. 151 type Port_Nbr is new Uns32; 152 subtype Port_Idx is Port_Nbr range 0 .. Port_Nbr'Last - 1; 153 154 type Port_Desc is record 155 -- Name of the port. 156 Name : Sname; 157 158 Is_Inout : Boolean; 159 160 -- Port width (number of bits). 161 W : Width; 162 end record; 163 pragma Pack (Port_Desc); 164 pragma Convention (C, Port_Desc); 165 166 type Port_Desc_Array is array (Port_Idx range <>) of Port_Desc; 167 168 type Param_Idx is new Uns32; 169 No_Param_Idx : constant Param_Idx := 0; 170 171 subtype Param_Nbr is Param_Idx range 0 .. Param_Idx'Last - 1; 172 173 -- Type of a parameter. As this is defined in a module, this is valid for 174 -- all instances. 175 -- NOTE: the corresponding C enum is built from this type using the 176 -- 'Param_' prefix and indentation. 177 type Param_Type is 178 ( 179 Param_Invalid, 180 181 -- An unsigned 32 bit value. 182 Param_Uns32, 183 184 -- A Generic value (with a hint of the type). This is a bit/logic 185 -- vector. 186 -- TODO: Replace Integer with Signed/Unsigned. 187 Param_Pval_Vector, 188 Param_Pval_String, 189 Param_Pval_Integer, 190 Param_Pval_Real, 191 Param_Pval_Time_Ps, 192 Param_Pval_Boolean 193 ); 194 pragma Convention (C, Param_Type); 195 196 subtype Param_Types_Pval is 197 Param_Type range Param_Pval_Vector .. Param_Pval_Boolean; 198 199 type Param_Desc is record 200 -- Name of the parameter 201 Name : Sname; 202 203 -- Type of the parameter 204 Typ : Param_Type; 205 end record; 206 207 type Param_Desc_Array is array (Param_Idx range <>) of Param_Desc; 208 209 -- Parameter value. 210 type Pval is private; 211 No_Pval : constant Pval; 212 213 -- Attribute of an instance. 214 type Attribute is private; 215 216 -- Subprograms for modules. 217 function New_Design (Name : Sname) return Module; 218 function New_User_Module (Parent : Module; 219 Name : Sname; 220 Id : Module_Id; 221 Nbr_Inputs : Port_Nbr; 222 Nbr_Outputs : Port_Nbr; 223 Nbr_Params : Param_Nbr := 0) 224 return Module; 225 procedure Set_Input_Desc (M : Module; I : Port_Idx; Desc : Port_Desc); 226 procedure Set_Output_Desc (M : Module; O : Port_Idx; Desc : Port_Desc); 227 procedure Set_Ports_Desc (M : Module; 228 Input_Descs : Port_Desc_Array; 229 Output_Descs : Port_Desc_Array); 230 procedure Set_Params_Desc (M : Module; 231 Params : Param_Desc_Array); 232 233 -- Be sure the record is passed by reference. 234 pragma Convention (C, Set_Input_Desc); 235 pragma Convention (C, Set_Output_Desc); 236 237 -- Create the self instance, once ports are defined. This is required if 238 -- the internal netlist will be defined. 239 function Create_Self_Instance (M : Module) return Instance; 240 241 function Get_Module_Name (M : Module) return Sname; 242 function Get_Id (M : Module) return Module_Id; 243 244 -- Number of fixed inputs/outputs. 245 -- For gates with variable number of inputs (like Concatn), use the 246 -- functions from Netlists.Utils. 247 function Get_Nbr_Inputs (M : Module) return Port_Nbr; 248 function Get_Nbr_Outputs (M : Module) return Port_Nbr; 249 250 function Get_Nbr_Params (M : Module) return Param_Nbr; 251 252 function Get_Input_Desc (M : Module; I : Port_Idx) return Port_Desc; 253 function Get_Output_Desc (M : Module; O : Port_Idx) return Port_Desc; 254 255 function Get_Param_Desc (M : Module; Param : Param_Idx) return Param_Desc; 256 257 function Get_Self_Instance (M : Module) return Instance; 258 function Get_First_Instance (M : Module) return Instance; 259 260 -- Linked list of sub-modules. 261 -- Use Modules to iterate. 262 function Get_First_Sub_Module (M : Module) return Module; 263 function Get_Next_Sub_Module (M : Module) return Module; 264 265 -- Instance 266 function New_Instance (Parent : Module; M : Module; Name : Sname) 267 return Instance; 268 -- For instances non-fixed number of inputs/outputs/params. 269 function New_Var_Instance (Parent : Module; 270 M : Module; 271 Name : Sname; 272 Nbr_Inputs : Port_Nbr; 273 Nbr_Outputs : Port_Nbr; 274 Nbr_Params : Param_Nbr) 275 return Instance; 276 277 -- Remove and free the unconnected instance INST. 278 procedure Remove_Instance (Inst : Instance); 279 280 function Is_Self_Instance (I : Instance) return Boolean; 281 function Get_Module (Inst : Instance) return Module; 282 function Get_Instance_Name (Inst : Instance) return Sname; 283 function Get_Instance_Parent (Inst : Instance) return Module; 284 function Get_Output (Inst : Instance; Idx : Port_Idx) return Net; 285 function Get_Input (Inst : Instance; Idx : Port_Idx) return Input; 286 function Get_Next_Instance (Inst : Instance) return Instance; 287 288 function Get_Param_Uns32 (Inst : Instance; Param : Param_Idx) return Uns32; 289 procedure Set_Param_Uns32 (Inst : Instance; Param : Param_Idx; Val : Uns32); 290 291 function Get_Param_Pval (Inst : Instance; Param : Param_Idx) return Pval; 292 procedure Set_Param_Pval (Inst : Instance; Param : Param_Idx; Val : Pval); 293 294 -- Each instance has a mark flag available for any algorithm. 295 -- Please leave this flag clean for the next user. 296 function Get_Mark_Flag (Inst : Instance) return Boolean; 297 procedure Set_Mark_Flag (Inst : Instance; Flag : Boolean); 298 299 -- Input 300 function Get_Input_Parent (I : Input) return Instance; 301 function Get_Port_Idx (I : Input) return Port_Idx; 302 function Get_Driver (I : Input) return Net; 303 function Get_Next_Sink (I : Input) return Input; 304 305 -- Net (Output) 306 function Get_Net_Parent (O : Net) return Instance; 307 function Get_Port_Idx (O : Net) return Port_Idx; 308 function Get_First_Sink (O : Net) return Input; 309 function Get_Width (N : Net) return Width; 310 311 -- Set the width of a net. This operation is possible only if the width 312 -- is unknown. 313 procedure Set_Width (N : Net; W : Width); 314 315 -- Connections. 316 procedure Connect (I : Input; O : Net); 317 procedure Disconnect (I : Input); 318 319 -- Reconnect all sinks of OLD to N. 320 procedure Redirect_Inputs (Old : Net; N : Net); 321 322 -- For Pval. 323 -- Create a 4-state Pval. LEN is the number of bits (cannot be 0). 324 function Create_Pval4 (Len : Uns32) return Pval; 325 -- Create a 2-state Pval. The value cannot have X or Z. 326 function Create_Pval2 (Len : Uns32) return Pval; 327 function Get_Pval_Length (P : Pval) return Uns32; 328 329 -- OFF is the word offset, from 0 to (len - 1) / 32. 330 function Read_Pval (P : Pval; Off : Uns32) return Logic_32; 331 procedure Write_Pval (P : Pval; Off : Uns32; Val : Logic_32); 332 333 -- Add an attribute to INST. 334 procedure Set_Attribute 335 (Inst : Instance; Id : Name_Id; Ptype : Param_Type; Pv : Pval); 336 337 -- Return the first attribute for INST. Returns No_Attribute if none. 338 function Get_First_Attribute (Inst : Instance) return Attribute; 339 340 -- Get name/type/value of an attribute. 341 function Get_Attribute_Name (Attr : Attribute) return Name_Id; 342 function Get_Attribute_Type (Attr : Attribute) return Param_Type; 343 function Get_Attribute_Pval (Attr : Attribute) return Pval; 344 345 -- Get the next attribute for the same instance. 346 function Get_Attribute_Next (Attr : Attribute) return Attribute; 347 348 -- Display some usage stats on the standard error. 349 procedure Disp_Stats; 350private 351 type Sname is new Uns32 range 0 .. 2**30 - 1; 352 No_Sname : constant Sname := 0; 353 354 -- We don't care about C compatible representation of Sname_Record. 355 pragma Warnings (Off, "*convention*"); 356 type Sname_Record is record 357 Kind : Sname_Kind; 358 Prefix : Sname; 359 Suffix : Uns32; 360 end record; 361 pragma Pack (Sname_Record); 362 for Sname_Record'Size use 2*32; 363 pragma Warnings (On, "*convention*"); 364 365 type Module is mod 2**30; 366 No_Module : constant Module := 0; 367 Free_Module : constant Module := 1; 368 369 function Is_Valid (M : Module) return Boolean; 370 371 type Port_Desc_Idx is new Uns32; 372 No_Port_Desc_Idx : constant Port_Desc_Idx := 0; 373 374 type Param_Desc_Idx is new Uns32; 375 No_Param_Desc_Idx : constant Param_Desc_Idx := 0; 376 377 type Input is new Uns32; 378 No_Input : constant Input := 0; 379 380 type Net is new Uns32; 381 No_Net : constant Net := 0; 382 383 type Instance is new Uns32; 384 No_Instance : constant Instance := 0; 385 386 type Attribute is new Uns32; 387 No_Attribute : Attribute := 0; 388 389 type Attribute_Record is record 390 Name : Name_Id; 391 Val : Pval; 392 Typ : Param_Type; 393 Chain : Attribute; 394 end record; 395 396 function Attribute_Hash (Params : Instance) return Hash_Value_Type; 397 function Attribute_Build (Params : Instance) return Instance; 398 function Attribute_Build_Value (Obj : Instance) return Attribute; 399 400 -- Per instance map of attribute. 401 -- The index is the sub-instance, the value is the attribute chain. 402 package Attribute_Maps is new Dyn_Maps 403 (Params_Type => Instance, 404 Object_Type => Instance, 405 Value_Type => Attribute, 406 Hash => Attribute_Hash, 407 Build => Attribute_Build, 408 Build_Value => Attribute_Build_Value, 409 Equal => "="); 410 411 type Attribute_Map_Acc is access Attribute_Maps.Instance; 412 413 type Module_Record is record 414 Parent : Module; 415 Name : Sname; 416 Id : Module_Id; 417 First_Port_Desc : Port_Desc_Idx; 418 Nbr_Inputs : Port_Nbr; 419 Nbr_Outputs : Port_Nbr; 420 First_Param_Desc : Param_Desc_Idx; 421 Nbr_Params : Param_Nbr; 422 423 -- First sub-module child. 424 First_Sub_Module : Module; 425 Last_Sub_Module : Module; 426 427 -- Sub-module brother. 428 Next_Sub_Module : Module; 429 430 -- List of instances. 431 -- The self instance is the first instance. 432 -- FIXME: use an array instead ? 433 First_Instance : Instance; 434 Last_Instance : Instance; 435 436 -- Map of instance (of this module) to its attributes. 437 Attrs : Attribute_Map_Acc; 438 end record; 439 440 function Get_First_Port_Desc (M : Module) return Port_Desc_Idx; 441 function Get_First_Output (Inst : Instance) return Net; 442 function Get_Port_Desc (Idx : Port_Desc_Idx) return Port_Desc; 443 444 function Get_Attributes (M : Module) return Attribute_Map_Acc; 445 446 function Is_Valid (I : Instance) return Boolean; 447 448 type Instance_Record is record 449 -- The instance is instantiated in Parent. 450 Parent : Module; 451 Has_Attr : Boolean; -- Set when there is at least one attribute. 452 Flag4 : Boolean; 453 454 -- Instances are in a doubly-linked list. 455 Prev_Instance : Instance; 456 Next_Instance : Instance; 457 458 -- For a self-instance, Klass is equal to Parent, and Name is No_Sname. 459 Klass : Module; 460 Flag5 : Boolean; 461 Flag6 : Boolean; 462 463 Name : Sname; 464 Flag_Mark : Boolean; 465 Flag2 : Boolean; 466 467 First_Param : Param_Idx; 468 First_Input : Input; 469 First_Output : Net; 470 end record; 471 pragma Pack (Instance_Record); 472 for Instance_Record'Size use 8*32; 473 474 procedure Set_Next_Instance (Inst : Instance; Next : Instance); 475 procedure Set_Prev_Instance (Inst : Instance; Prev : Instance); 476 477 -- Procedures to rewrite the list of instances of a module: 478 -- * first extract the chain of instances from module M (and reset the 479 -- list of instances - so there is none), 480 -- * then add the ones to keep. 481 -- The list of instances is walked by using Get_Next_Instance. 482 procedure Extract_All_Instances (M : Module; First_Instance : out Instance); 483 procedure Append_Instance (M : Module; Inst : Instance); 484 485 -- Extract INST from the list of instance of its module. 486 -- Will still be connected, but won't appear anymore in the list of 487 -- instances. 488 -- Once extracted, the instance is not in a consistent state anymore. So 489 -- it should be either fully disconnected and freed or re-inserted in the 490 -- parent module. 491 procedure Extract_Instance (Inst : Instance); 492 493 -- Mark INST as free. Must be unconnected and removed from its module. 494 procedure Free_Instance (Inst : Instance); 495 496 type Input_Record is record 497 Parent : Instance; 498 Driver : Net; 499 Next_Sink : Input; 500 end record; 501 502 function Is_Valid (N : Net) return Boolean; 503 504 type Net_Record is record 505 Parent : Instance; 506 First_Sink : Input; 507 W : Width; 508 end record; 509 510 type Pval is new Uns32; 511 No_Pval : constant Pval := 0; 512 513end Netlists; 514