/* * yosys -- Yosys Open SYnthesis Suite * * Copyright (C) 2012 Clifford Wolf * * Permission to use, copy, modify, and/or distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. * */ #include "kernel/yosys.h" #include "kernel/sigtools.h" USING_YOSYS_NAMESPACE PRIVATE_NAMESPACE_BEGIN #define COST_MUX2 100 #define COST_MUX4 220 #define COST_MUX8 460 #define COST_MUX16 940 struct MuxcoverWorker { Module *module; SigMap sigmap; struct newmux_t { int cost; vector inputs, selects; newmux_t() : cost(0) {} }; struct tree_t { SigBit root; dict muxes; dict newmuxes; }; vector tree_list; dict, tuple, bool>> decode_mux_cache; dict> decode_mux_reverse_cache; int decode_mux_counter; bool use_mux4; bool use_mux8; bool use_mux16; bool nodecode; MuxcoverWorker(Module *module) : module(module), sigmap(module) { use_mux4 = false; use_mux8 = false; use_mux16 = false; nodecode = false; decode_mux_counter = 0; } void treeify() { pool roots; pool used_once; dict sig_to_mux; for (auto wire : module->wires()) { if (!wire->port_output) continue; for (auto bit : sigmap(wire)) roots.insert(bit); } for (auto cell : module->cells()) { for (auto conn : cell->connections()) { if (!cell->input(conn.first)) continue; for (auto bit : sigmap(conn.second)) { if (used_once.count(bit) || cell->type != "$_MUX_" || conn.first == "\\S") roots.insert(bit); used_once.insert(bit); } } if (cell->type == "$_MUX_") sig_to_mux[sigmap(cell->getPort("\\Y"))] = cell; } log(" Treeifying %d MUXes:\n", GetSize(sig_to_mux)); roots.sort(); for (auto rootsig : roots) { tree_t tree; tree.root = rootsig; pool wavefront; wavefront.insert(rootsig); while (!wavefront.empty()) { SigBit bit = wavefront.pop(); if (sig_to_mux.count(bit) && (bit == rootsig || !roots.count(bit))) { Cell *c = sig_to_mux.at(bit); tree.muxes[bit] = c; wavefront.insert(sigmap(c->getPort("\\A"))); wavefront.insert(sigmap(c->getPort("\\B"))); } } if (!tree.muxes.empty()) { log(" Found tree with %d MUXes at root %s.\n", GetSize(tree.muxes), log_signal(tree.root)); tree_list.push_back(tree); } } log(" Finished treeification: Found %d trees.\n", GetSize(tree_list)); } bool follow_muxtree(SigBit &ret_bit, tree_t &tree, SigBit bit, const char *path) { if (*path) { if (tree.muxes.count(bit) == 0) return false; char port_name[3] = {'\\', *path, 0}; return follow_muxtree(ret_bit, tree, sigmap(tree.muxes.at(bit)->getPort(port_name)), path+1); } else { ret_bit = bit; return true; } } int prepare_decode_mux(SigBit &A, SigBit B, SigBit sel, SigBit bit) { if (A == B) return 0; tuple key(A, B, sel); if (decode_mux_cache.count(key) == 0) { auto &entry = decode_mux_cache[key]; std::get<0>(entry) = module->addWire(NEW_ID); std::get<2>(entry) = false; decode_mux_reverse_cache[std::get<0>(entry)] = key; } auto &entry = decode_mux_cache[key]; A = std::get<0>(entry); std::get<1>(entry).insert(bit); if (std::get<2>(entry)) return 0; return COST_MUX2 / GetSize(std::get<1>(entry)); } void implement_decode_mux(SigBit ctrl_bit) { if (decode_mux_reverse_cache.count(ctrl_bit) == 0) return; auto &key = decode_mux_reverse_cache.at(ctrl_bit); auto &entry = decode_mux_cache[key]; if (std::get<2>(entry)) return; implement_decode_mux(std::get<0>(key)); implement_decode_mux(std::get<1>(key)); module->addMuxGate(NEW_ID, std::get<0>(key), std::get<1>(key), std::get<2>(key), ctrl_bit); std::get<2>(entry) = true; decode_mux_counter++; } int find_best_cover(tree_t &tree, SigBit bit) { if (tree.newmuxes.count(bit)) { return tree.newmuxes.at(bit).cost; } SigBit A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P; SigBit S1, S2, S3, S4, S5, S6, S7, S8; SigBit T1, T2, T3, T4; SigBit U1, U2; SigBit V1; newmux_t best_mux; bool ok = true; // 2-Input MUX ok = ok && follow_muxtree(A, tree, bit, "A"); ok = ok && follow_muxtree(B, tree, bit, "B"); ok = ok && follow_muxtree(S1, tree, bit, "S"); if (ok) { newmux_t mux; mux.inputs.push_back(A); mux.inputs.push_back(B); mux.selects.push_back(S1); mux.cost += COST_MUX2; mux.cost += find_best_cover(tree, A); mux.cost += find_best_cover(tree, B); best_mux = mux; } // 4-Input MUX if (use_mux4) { ok = ok && follow_muxtree(A, tree, bit, "AA"); ok = ok && follow_muxtree(B, tree, bit, "AB"); ok = ok && follow_muxtree(C, tree, bit, "BA"); ok = ok && follow_muxtree(D, tree, bit, "BB"); ok = ok && follow_muxtree(S1, tree, bit, "AS"); ok = ok && follow_muxtree(S2, tree, bit, "BS"); if (nodecode) ok = ok && S1 == S2; ok = ok && follow_muxtree(T1, tree, bit, "S"); if (ok) { newmux_t mux; mux.inputs.push_back(A); mux.inputs.push_back(B); mux.inputs.push_back(C); mux.inputs.push_back(D); mux.cost += prepare_decode_mux(S1, S2, T1, bit); mux.selects.push_back(S1); mux.selects.push_back(T1); mux.cost += COST_MUX4; mux.cost += find_best_cover(tree, A); mux.cost += find_best_cover(tree, B); mux.cost += find_best_cover(tree, C); mux.cost += find_best_cover(tree, D); if (best_mux.cost > mux.cost) best_mux = mux; } } // 8-Input MUX if (use_mux8) { ok = ok && follow_muxtree(A, tree, bit, "AAA"); ok = ok && follow_muxtree(B, tree, bit, "AAB"); ok = ok && follow_muxtree(C, tree, bit, "ABA"); ok = ok && follow_muxtree(D, tree, bit, "ABB"); ok = ok && follow_muxtree(E, tree, bit, "BAA"); ok = ok && follow_muxtree(F, tree, bit, "BAB"); ok = ok && follow_muxtree(G, tree, bit, "BBA"); ok = ok && follow_muxtree(H, tree, bit, "BBB"); ok = ok && follow_muxtree(S1, tree, bit, "AAS"); ok = ok && follow_muxtree(S2, tree, bit, "ABS"); ok = ok && follow_muxtree(S3, tree, bit, "BAS"); ok = ok && follow_muxtree(S4, tree, bit, "BBS"); if (nodecode) ok = ok && S1 == S2 && S2 == S3 && S3 == S4; ok = ok && follow_muxtree(T1, tree, bit, "AS"); ok = ok && follow_muxtree(T2, tree, bit, "BS"); if (nodecode) ok = ok && T1 == T2; ok = ok && follow_muxtree(U1, tree, bit, "S"); if (ok) { newmux_t mux; mux.inputs.push_back(A); mux.inputs.push_back(B); mux.inputs.push_back(C); mux.inputs.push_back(D); mux.inputs.push_back(E); mux.inputs.push_back(F); mux.inputs.push_back(G); mux.inputs.push_back(H); mux.cost += prepare_decode_mux(S1, S2, T1, bit); mux.cost += prepare_decode_mux(S3, S4, T2, bit); mux.cost += prepare_decode_mux(S1, S3, U1, bit); mux.cost += prepare_decode_mux(T1, T2, U1, bit); mux.selects.push_back(S1); mux.selects.push_back(T1); mux.selects.push_back(U1); mux.cost += COST_MUX8; mux.cost += find_best_cover(tree, A); mux.cost += find_best_cover(tree, B); mux.cost += find_best_cover(tree, C); mux.cost += find_best_cover(tree, D); mux.cost += find_best_cover(tree, E); mux.cost += find_best_cover(tree, F); mux.cost += find_best_cover(tree, G); mux.cost += find_best_cover(tree, H); if (best_mux.cost > mux.cost) best_mux = mux; } } // 16-Input MUX if (use_mux16) { ok = ok && follow_muxtree(A, tree, bit, "AAAA"); ok = ok && follow_muxtree(B, tree, bit, "AAAB"); ok = ok && follow_muxtree(C, tree, bit, "AABA"); ok = ok && follow_muxtree(D, tree, bit, "AABB"); ok = ok && follow_muxtree(E, tree, bit, "ABAA"); ok = ok && follow_muxtree(F, tree, bit, "ABAB"); ok = ok && follow_muxtree(G, tree, bit, "ABBA"); ok = ok && follow_muxtree(H, tree, bit, "ABBB"); ok = ok && follow_muxtree(I, tree, bit, "BAAA"); ok = ok && follow_muxtree(J, tree, bit, "BAAB"); ok = ok && follow_muxtree(K, tree, bit, "BABA"); ok = ok && follow_muxtree(L, tree, bit, "BABB"); ok = ok && follow_muxtree(M, tree, bit, "BBAA"); ok = ok && follow_muxtree(N, tree, bit, "BBAB"); ok = ok && follow_muxtree(O, tree, bit, "BBBA"); ok = ok && follow_muxtree(P, tree, bit, "BBBB"
--  Nodes recognizer for ieee.std_logic_arith.
--  Copyright (C) 2019 Tristan Gingold
--
--  GHDL 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, or (at your option) any later
--  version.
--
--  GHDL 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 GHDL; see the file COPYING.  If not, write to the Free
--  Software Foundation, 59 Temple Place - Suite 330, Boston, MA
--  02111-1307, USA.

with Types; use Types;
with Vhdl.Std_Package;
with Std_Names; use Std_Names;
with Vhdl.Errors; use Vhdl.Errors;
with Vhdl.Ieee.Std_Logic_1164;

package body Vhdl.Ieee.Std_Logic_Arith is
   --  Unsigned and signed type definition.
   Unsigned_Type : Iir := Null_Iir;
   Signed_Type : Iir := Null_Iir;

   type Arg_Kind is (Type_Signed, Type_Unsigned, Type_Int, Type_Log, Type_Slv);

   subtype Conv_Arg_Kind is Arg_Kind range Type_Signed .. Type_Log;
   type Conv_Pattern_Type is
     array (Conv_Arg_Kind) of Iir_Predefined_Functions;

   Conv_Uns_Patterns : constant Conv_Pattern_Type :=
     (Iir_Predefined_Ieee_Std_Logic_Arith_Conv_Unsigned_Sgn,
      Iir_Predefined_Ieee_Std_Logic_Arith_Conv_Unsigned_Uns,
      Iir_Predefined_Ieee_Std_Logic_Arith_Conv_Unsigned_Int,
      Iir_Predefined_Ieee_Std_Logic_Arith_Conv_Unsigned_Log);

   Conv_Int_Patterns : constant Conv_Pattern_Type :=
     (Iir_Predefined_Ieee_Std_Logic_Arith_Conv_Integer_Sgn,
      Iir_Predefined_Ieee_Std_Logic_Arith_Conv_Integer_Uns,
      Iir_Predefined_Ieee_Std_Logic_Arith_Conv_Integer_Int,
      Iir_Predefined_Ieee_Std_Logic_Arith_Conv_Integer_Log);

   Error : exception;

   procedure Extract_Declarations (Pkg : Iir_Package_Declaration)
   is
      procedure Classify_Arg (Arg : Iir; Kind : out Arg_Kind)
      is
         Arg_Type : constant Iir := Get_Type (Arg);
      begin
         if Arg_Type = Signed_Type then
            Kind := Type_Signed;
         elsif Arg_Type = Unsigned_Type then
            Kind := Type_Unsigned;
         elsif Arg_Type = Vhdl.Std_Package.Integer_Subtype_Definition then
            Kind := Type_Int;
         elsif Arg_Type = Ieee.Std_Logic_1164.Std_Ulogic_Type then
            Kind := Type_Log;
         elsif Arg_Type = Ieee.Std_Logic_1164.Std_Logic_Vector_Type then
            Kind := Type_Slv;
         else
            raise Error;
         end if;
      end Classify_Arg;

      Decl : Iir;
      Type_Def : Iir;

      Arg1, Arg2 : Iir;
      Arg1_Kind, Arg2_Kind : Arg_Kind;

      function Handle_Conv (Pats : Conv_Pattern_Type)
                           return Iir_Predefined_Functions is
      begin
         if Arg2_Kind /= Type_Int then
            raise Error;
         end if;
         return Pats (Arg1_Kind);
      end Handle_Conv;

      Def : Iir_Predefined_Functions;
   begin
      Decl := Get_Declaration_Chain (Pkg);

      if Decl /= Null_Iir
        and then Get_Kind (Decl) = Iir_Kind_Use_Clause
      then
         --  Mentor version.  Don't extract and don't crash.
         return;
      end if;

      --  The first declaration should be type Unsigned.
      if not (Decl /= Null_Iir
                and then Get_Kind (Decl) = Iir_Kind_Type_Declaration
                and then Get_Identifier (Decl) = Name_Unsigned)
      then
         raise Error;
      end if;

      Type_Def := Get_Type_Definition (Decl);
      if Get_Kind (Type_Def) /= Iir_Kind_Array_Type_Definition then
         raise Error;
      end if;
      Unsigned_Type := Type_Def;

      --  The second declaration should be type Signed.
      Decl := Get_Chain (Decl);
      Decl := Skip_Implicit (Decl);
      if not (Decl /= Null_Iir
                and then Get_Kind (Decl) = Iir_Kind_Type_Declaration
                and then Get_Identifier (Decl) = Name_Signed)
      then
         raise Error;
      end if;

      Type_Def := Get_Type_Definition (Decl);
      if Get_Kind (Type_Def) /= Iir_Kind_Array_Type_Definition then
         raise Error;
      end if;
      Signed_Type := Type_Def;

      --  Skip subtypes
      Decl := Get_Chain (Decl);
      Decl := Skip_Implicit (Decl);
      while Is_Valid (Decl) loop
         exit when Get_Kind (Decl) /= Iir_Kind_Subtype_Declaration;
         Decl := Get_Chain (Decl);
      end loop;

      --  Handle functions.
      while Is_Valid (Decl) loop
         Def := Iir_Predefined_None;

         case Get_Kind (Decl) is
            when Iir_Kind_Function_Declaration =>
               Arg1 := Get_Interface_Declaration_Chain (Decl);
               if Is_Null (Arg1) then
                  raise Error;
               end if;

               Classify_Arg (Arg1, Arg1_Kind);
               Arg2 := Get_Chain (Arg1);
               if Is_Valid (Arg2) then
                  --  Dyadic function.
                  Classify_Arg (Arg2, Arg2_Kind);

                  case Get_Identifier (Decl) is
                     when Name_Conv_Unsigned =>
                        Def := Handle_Conv (Conv_Uns_Patterns);
                     when others =>
                        null;
                  end case;
               else
                  --  Monadic function.
                  case Get_Identifier (Decl) is
                     when Name_Conv_Integer =>
                        Def := Conv_Int_Patterns (Arg1_Kind);
                     when others =>
                        null;
                  end case;
               end if;

            when Iir_Kind_Non_Object_Alias_Declaration
              | Iir_Kind_Procedure_Declaration =>
               null;

            when others =>
               raise Error;
         end case;
         Set_Implicit_Definition (Decl, Def);

         Decl := Get_Chain (Decl);
      end loop;
   exception
      when Error =>
         Error_Msg_Sem (+Pkg, "package ieee.std_logic_arith is ill-formed");
   end Extract_Declarations;
end Vhdl.Ieee.Std_Logic_Arith;