kernel/ffmerge.h

   1 /*
   2  *  yosys -- Yosys Open SYnthesis Suite
   3  *
   4  *  Copyright (C) 2021  Marcelina Kościelnicka <mwk@0x04.net>
   5  *
   6  *  Permission to use, copy, modify, and/or distribute this software for any
   7  *  purpose with or without fee is hereby granted, provided that the above
   8  *  copyright notice and this permission notice appear in all copies.
   9  *
  10  *  THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  *  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  *  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  *  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  *  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  *  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  *  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  *
  18  */
  19
  20 #ifndef FFMERGE_H
  21 #define FFMERGE_H
  22
  23 #include "kernel/ffinit.h"
  24 #include "kernel/ff.h"
  25
  26 YOSYS_NAMESPACE_BEGIN
  27
  28 // A helper class for passes that want to merge FFs on the input or output
  29 // of a cell into the cell itself.
  30 //
  31 // The procedure is:
  32 //
  33 // 1. Construct this class (at beginning of processing for a given module).
  34 // 2. For every considered cell:
  35 //
  36 //    a. Call find_output_ff for every considered output.
  37 //    b. Call find_input_ff for every considered input.
  38 //    c. Look at the FF description returned (if any) from each call, reject
  39 //       results that cannot be merged into given cell for any reason.
  40 //       If both inputs and outputs are being merged, take care of FF bits that
  41 //       are returned in both input and output results (a FF bit cannot be
  42 //       merged to both).  Decide on the final set of FF bits to merge.
  43 //    d. Call remove_output_ff for every find_output_ff result that will be used
  44 //       for merging.  This removes the actual FF bits from design and from index.
  45 //    e. Call mark_input_ff for every find_input_ff result that will be used
  46 //       for merging.  This updates the index disallowing further usage of these
  47 //       FF bits for output FF merging, if they were eligible before.  The actual
  48 //       FF bits are still left in the design and can be merged into other inputs.
  49 //       If the FF bits are not otherwise used, they will be removed by later
  50 //       opt passes.
  51 //    f. Merge the FFs into the cell.
  52 //
  53 // Note that, if both inputs and outputs are being considered for merging in
  54 // a single pass, the result may be nondeterministic (depending on cell iteration
  55 // order) because a given FF bit could be eligible for both input and output merge,
  56 // perhaps in different cells.  For this reason, it may be a good idea to separate
  57 // input and output merging.
  58
  59 struct FfMergeHelper
  60 {
  61         const SigMap *sigmap;
  62         RTLIL::Module *module;
  63         FfInitVals *initvals;
  64
  65         dict<SigBit, std::pair<Cell*, int>> dff_driver;
  66         dict<SigBit, pool<std::pair<Cell*, int>>> dff_sink;
  67         dict<SigBit, int> sigbit_users_count;
  68
  69         // Returns true if all bits in sig are completely unused.
  70         bool is_output_unused(RTLIL::SigSpec sig);
  71
  72         // Finds the FF to merge into a given cell output.  Takes sig, which
  73         // is the current cell output — it will be the sig_d of the found FF.
  74         // If found, returns true, and fills the two output arguments.
  75         //
  76         // For every bit of sig, this function finds a FF bit that has
  77         // the same sig_d, and fills the output FfData according to the FF
  78         // bits found.  This function will only consider FF bits that are
  79         // the only user of the given sig bits — if any bit in sig is used
  80         // by anything other than a single FF, this function will return false.
  81         //
  82         // The returned FfData structure does not correspond to any actual FF
  83         // cell in the design — it is the amalgamation of extracted FF bits,
  84         // possibly coming from several FF cells.
  85         //
  86         // If some of the bits in sig have no users at all, this function
  87         // will accept them as well (and fill returned FfData with dummy values
  88         // for the given bit, effectively synthesizing an unused FF bit of the
  89         // appropriate type).  However, if all bits in sig are completely
  90         // unused, this function will fail and return false (having no idea
  91         // what kind of FF to produce) — use the above helper if that case
  92         // is important to handle.
  93         //
  94         // Note that this function does not remove the FF bits returned from
  95         // the design — this is so that the caller can decide whether to accept
  96         // this FF for merging or not.  If the result is accepted,
  97         // remove_output_ff should be called on the second output argument.
  98         bool find_output_ff(RTLIL::SigSpec sig, FfData &ff, pool<std::pair<Cell *, int>> &bits);
  99
 100         // Like above, but returns a FF to merge into a given cell input.  Takes
 101         // sig_q, which is the current cell input — it will search for FFs with
 102         // matching sig_q.
 103         //
 104         // As opposed to find_output_ff, this function doesn't care about usage
 105         // counts, and may return FF bits that also have other fanout.  This
 106         // should not be a problem for input FF merging.
 107         //
 108         // As a special case, if some of the bits in sig_q are constant, this
 109         // function will accept them as well, by synthesizing in-place
 110         // a constant-input FF bit (with matching initial value and reset value).
 111         // However, this will not work if the input is all-constant — if the caller
 112         // cares about this case, it needs to check for it explicitely.
 113         bool find_input_ff(RTLIL::SigSpec sig, FfData &ff, pool<std::pair<Cell *, int>> &bits);
 114
 115         // To be called on find_output_ff result that will be merged.  This
 116         // marks the given FF bits as used up (and not to be considered for
 117         // further merging as inputs), and reconnects their Q ports to a dummy
 118         // wire (since the wire previously connected there will now be driven
 119         // by the merged-to cell instead).
 120         void remove_output_ff(const pool<std::pair<Cell *, int>> &bits);
 121
 122         // To be called on find_input_ff result that will be merged.  This
 123         // marks the given FF bits as used, and disallows merging them as
 124         // outputs.  They can, however, still be merged as inputs again
 125         // (perhaps for another cell).
 126         void mark_input_ff(const pool<std::pair<Cell *, int>> &bits);
 127
 128         void set(FfInitVals *initvals_, RTLIL::Module *module_);
 129
 130         void clear();
 131
 132         FfMergeHelper(FfInitVals *initvals, RTLIL::Module *module) {
 133                 set(initvals, module);
 134         }
 135
 136         FfMergeHelper() {}
 137 };
 138
 139 YOSYS_NAMESPACE_END
 140
 141 #endif