Merge pull request #757 from antmicro/lut-mapping-cache

interchange: Add caching of site LUT mapping solution

8 files changed, 510 insertions, 74 deletions

diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc
index d67f54fd..a39f49e6 100644
--- a/fpga_interchange/arch.cc
+++ b/fpga_interchange/arch.cc
@@ -814,6 +814,14 @@ bool Arch::place()
     getCtx()->attrs[getCtx()->id("step")] = std::string("place");
     archInfoToAttributes();
 
+    // Print site LUT mapping caching stats
+    if (!getCtx()->arch_args.disable_lut_mapping_cache) {
+        log_info("Site LUT mapping cache stats:\n");
+        log_info("    miss ratio: %.1f%%\n", getCtx()->site_lut_mapping_cache.getMissRatio() * 100.0f);
+        log_info("    peak size : %zuMB (%zu items)\n", getCtx()->site_lut_mapping_cache.getSizeMB(),
+                 getCtx()->site_lut_mapping_cache.getCount());
+    }
+
     getCtx()->check();
 
     return true;
@@ -837,6 +845,9 @@ static void prepare_sites_for_routing(Context *ctx)
     // pins to ensure a routeable pin choice.
     ctx->site_routing_cache.clear();
 
+    // Clear the LUT mapping cache
+    ctx->site_lut_mapping_cache.clear();
+
     // Have site router bind site routing (via bindPip and bindWire).
     // This is important so that the pseudo pips are correctly blocked prior
     // to handing the design to the generalized router algorithms.
diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h
index 8afb71e1..0fb4f462 100644
--- a/fpga_interchange/arch.h
+++ b/fpga_interchange/arch.h
@@ -39,6 +39,7 @@
 #include "dedicated_interconnect.h"
 #include "lookahead.h"
 #include "pseudo_pip_model.h"
+#include "site_lut_mapping_cache.h"
 #include "site_router.h"
 #include "site_routing_cache.h"
 
@@ -50,6 +51,7 @@ struct ArchArgs
     std::string package;
     bool rebuild_lookahead;
     bool dont_write_lookahead;
+    bool disable_lut_mapping_cache;
 };
 
 struct ArchRanges
@@ -1133,6 +1135,7 @@ struct Arch : ArchAPI<ArchRanges>
     Lookahead lookahead;
     mutable RouteNodeStorage node_storage;
     mutable SiteRoutingCache site_routing_cache;
+    mutable SiteLutMappingCache site_lut_mapping_cache;
     bool disallow_site_routing;
     CellParameters cell_parameters;
 
diff --git a/fpga_interchange/luts.cc b/fpga_interchange/luts.cc
index 0156d379..d9e17ca9 100644
--- a/fpga_interchange/luts.cc
+++ b/fpga_interchange/luts.cc
@@ -22,6 +22,8 @@
 #include "log.h"
 #include "nextpnr.h"
 
+#include "site_lut_mapping_cache.h"
+
 //#define DEBUG_LUT_ROTATION
 
 NEXTPNR_NAMESPACE_BEGIN
@@ -253,7 +255,8 @@ uint32_t LutMapper::check_wires(const std::vector<std::vector<int32_t>> &bel_to_
     return vcc_mask;
 }
 
-bool LutMapper::remap_luts(const Context *ctx, pool<const LutBel *, hash_ptr_ops> *blocked_luts)
+bool LutMapper::remap_luts(const Context *ctx, SiteLutMappingResult *lut_mapping,
+                           pool<const LutBel *, hash_ptr_ops> *blocked_luts)
 {
     dict<NetInfo *, LutPin, hash_ptr_ops> lut_pin_map;
     std::vector<const LutBel *> lut_bels;
@@ -377,32 +380,9 @@ bool LutMapper::remap_luts(const Context *ctx, pool<const LutBel *, hash_ptr_ops
         }
     }
 
-    // Push new cell -> BEL pin maps out to cells now that equations have been
-    // verified!
-    for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
-        CellInfo *cell = cells[cell_idx];
-        auto &lut_bel = *lut_bels[cell_idx];
-
-        for (size_t pin_idx = 0; pin_idx < cell->lut_cell.pins.size(); ++pin_idx) {
-            auto &bel_pins = cell->cell_bel_pins[cell->lut_cell.pins[pin_idx]];
-            bel_pins.clear();
-            bel_pins.push_back(lut_bel.pins[cell_to_bel_pin_remaps[cell_idx][pin_idx]]);
-        }
-    }
-
-    if (cells.size() == element.lut_bels.size()) {
-        for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
-            CellInfo *cell = cells[cell_idx];
-            auto &lut_bel = *lut_bels[cell_idx];
-            cell->lut_cell.vcc_pins.clear();
-            for (size_t bel_pin_idx = 0; bel_pin_idx < lut_bel.pins.size(); ++bel_pin_idx) {
-                if ((used_pins & (1 << bel_pin_idx)) == 0) {
-                    NPNR_ASSERT(bel_to_cell_pin_remaps[cell_idx][bel_pin_idx] == -1);
-                    cell->lut_cell.vcc_pins.emplace(lut_bel.pins.at(bel_pin_idx));
-                }
-            }
-        }
-    } else {
+    // Not all LUT inputs are used
+    uint32_t vcc_pins = 0;
+    if (cells.size() != element.lut_bels.size()) {
         // Look to see if wires can be run from element inputs to unused
         // outputs. If not, block the BEL pin by tying to VCC.
         //
@@ -411,7 +391,7 @@ bool LutMapper::remap_luts(const Context *ctx, pool<const LutBel *, hash_ptr_ops
         //
         // Use Arch::prefered_constant_net_type to determine what
         // constant net should be used for unused pins.
-        uint32_t vcc_pins = check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins, blocked_luts);
+        vcc_pins = check_wires(bel_to_cell_pin_remaps, lut_bels, used_pins, blocked_luts);
 #if defined(DEBUG_LUT_ROTATION)
         log_info("vcc_pins = 0x%x", vcc_pins);
         for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
@@ -420,34 +400,52 @@ bool LutMapper::remap_luts(const Context *ctx, pool<const LutBel *, hash_ptr_ops
         }
         log("\n");
 #endif
+    }
 
-        for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
-            CellInfo *cell = cells[cell_idx];
-            auto &lut_bel = *lut_bels[cell_idx];
-            cell->lut_cell.vcc_pins.clear();
-            for (size_t bel_pin_idx = 0; bel_pin_idx < lut_bel.pins.size(); ++bel_pin_idx) {
-                if ((vcc_pins & (1 << bel_pin_idx)) != 0) {
+    // Fill in the LUT mapping result
+
+    // Push new cell -> BEL pin maps out to cells now that equations have been
+    // verified!
+    lut_mapping->cells.reserve(cells.size());
+    for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
+        CellInfo *cellInfo = cells[cell_idx];
+        auto &lutBel = *lut_bels[cell_idx];
+
+        // Add the cell data
+        SiteLutMappingResult::Cell cell;
+        cell.belIndex = cellInfo->bel.index;
+
+        // Cell to BEL pin map
+        for (size_t pin_idx = 0; pin_idx < cellInfo->lut_cell.pins.size(); ++pin_idx) {
+            IdString cellPin = cellInfo->lut_cell.pins[pin_idx];
+            IdString belPin = lutBel.pins[cell_to_bel_pin_remaps[cell_idx][pin_idx]];
+            cell.belPins[cellPin] = belPin;
+        }
+
+        cell.lutCell.vcc_pins.clear();
+
+        // All LUT inputs used
+        if (cells.size() == element.lut_bels.size()) {
+            for (size_t bel_pin_idx = 0; bel_pin_idx < lutBel.pins.size(); ++bel_pin_idx) {
+                if ((used_pins & (1 << bel_pin_idx)) == 0) {
                     NPNR_ASSERT(bel_to_cell_pin_remaps[cell_idx][bel_pin_idx] == -1);
-                    auto pin = lut_bel.pins.at(bel_pin_idx);
-                    cell->lut_cell.vcc_pins.emplace(pin);
+                    cell.lutCell.vcc_pins.emplace(lutBel.pins.at(bel_pin_idx));
                 }
             }
         }
-    }
-
-#ifdef DEBUG_LUT_ROTATION
-    log_info("Final mapping:\n");
-    for (size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
-        CellInfo *cell = cells[cell_idx];
-        for (auto &cell_pin_pair : cell->cell_bel_pins) {
-            log_info("%s %s %s =>", cell->type.c_str(ctx), cell->name.c_str(ctx), cell_pin_pair.first.c_str(ctx));
-            for (auto bel_pin : cell_pin_pair.second) {
-                log(" %s", bel_pin.c_str(ctx));
+        // Only some LUT inputs used
+        else {
+            for (size_t bel_pin_idx = 0; bel_pin_idx < lutBel.pins.size(); ++bel_pin_idx) {
+                if ((vcc_pins & (1 << bel_pin_idx)) != 0) {
+                    NPNR_ASSERT(bel_to_cell_pin_remaps[cell_idx][bel_pin_idx] == -1);
+                    auto pin = lutBel.pins.at(bel_pin_idx);
+                    cell.lutCell.vcc_pins.emplace(pin);
+                }
             }
-            log("\n");
         }
+
+        lut_mapping->cells.push_back(cell);
     }
-#endif
 
     return true;
 }
diff --git a/fpga_interchange/luts.h b/fpga_interchange/luts.h
index cbb817c9..8f33507a 100644
--- a/fpga_interchange/luts.h
+++ b/fpga_interchange/luts.h
@@ -31,6 +31,8 @@ NEXTPNR_NAMESPACE_BEGIN
 struct CellInfo;
 struct Context;
 
+struct SiteLutMappingResult;
+
 enum LogicLevel
 {
     LL_Zero,
@@ -66,6 +68,14 @@ struct LutBel
     int32_t max_pin;
 };
 
+struct SiteLutMapping
+{
+    struct LutCellMapping
+    {
+        LutCell lut_cell;
+    };
+};
+
 // Work forward from cell definition and cell -> bel pin map and check that
 // equation is valid.
 void check_equation(const LutCell &lut_cell, const dict<IdString, IdString> &cell_to_bel_map, const LutBel &lut_bel,
@@ -89,7 +99,8 @@ struct LutMapper
 
     std::vector<CellInfo *> cells;
 
-    bool remap_luts(const Context *ctx, pool<const LutBel *, hash_ptr_ops> *blocked_luts);
+    bool remap_luts(const Context *ctx, SiteLutMappingResult *lut_mapping,
+                    pool<const LutBel *, hash_ptr_ops> *blocked_luts);
 
     // Determine which wires given the current mapping must be tied to the
     // default constant.
diff --git a/fpga_interchange/main.cc b/fpga_interchange/main.cc
index 64a15e62..5423c17d 100644
--- a/fpga_interchange/main.cc
+++ b/fpga_interchange/main.cc
@@ -57,6 +57,7 @@ po::options_description FpgaInterchangeCommandHandler::getArchOptions()
     specific.add_options()("package", po::value<std::string>(), "Package to use");
     specific.add_options()("rebuild-lookahead", "Ignore lookahead cache and rebuild");
     specific.add_options()("dont-write-lookahead", "Don't write the lookahead file");
+    specific.add_options()("disable-lut-mapping-cache", "Disable caching of LUT mapping solutions in site router");
 
     return specific;
 }
@@ -76,6 +77,7 @@ std::unique_ptr<Context> FpgaInterchangeCommandHandler::createContext(dict<std::
     ArchArgs chipArgs;
     chipArgs.rebuild_lookahead = vm.count("rebuild_lookahead") != 0;
     chipArgs.dont_write_lookahead = vm.count("dont_write_lookahead") != 0;
+    chipArgs.disable_lut_mapping_cache = vm.count("disable-lut-mapping-cache") != 0;
 
     if (!vm.count("chipdb")) {
         log_error("chip database binary must be provided\n");
diff --git a/fpga_interchange/site_lut_mapping_cache.cc b/fpga_interchange/site_lut_mapping_cache.cc
new file mode 100644
index 00000000..0cf741f2
--- /dev/null
+++ b/fpga_interchange/site_lut_mapping_cache.cc
@@ -0,0 +1,196 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2021  Symbiflow Authors
+ *
+ *  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 "site_lut_mapping_cache.h"
+#include "nextpnr.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+// ============================================================================
+
+SiteLutMappingKey SiteLutMappingKey::create(const SiteInformation &siteInfo)
+{
+    const Context *ctx = siteInfo.ctx;
+
+    // Look for LUT cells in the site
+    std::vector<CellInfo *> lutCells;
+    lutCells.reserve(siteInfo.cells_in_site.size());
+
+    for (CellInfo *cellInfo : siteInfo.cells_in_site) {
+
+        // Not a LUT cell
+        if (cellInfo->lut_cell.pins.empty()) {
+            continue;
+        }
+
+        // Not bound to a LUT BEL
+        BelId bel = cellInfo->bel;
+        const auto &bel_data = bel_info(ctx->chip_info, bel);
+        if (bel_data.lut_element == -1) {
+            continue;
+        }
+
+        lutCells.push_back(cellInfo);
+    }
+
+    // Sort cells by BEL indices to maintain always the same order
+    std::sort(lutCells.begin(), lutCells.end(),
+              [](const CellInfo *a, const CellInfo *b) { return a->bel.index > b->bel.index; });
+
+    // Initialize the key
+    SiteLutMappingKey key;
+    key.tileType = siteInfo.tile_type;
+    key.siteType = ctx->chip_info->sites[siteInfo.site].site_type;
+    key.numCells = 0;
+
+    // Get bound nets. Store localized (to the LUT cluster) net indices only
+    // to get always the same key for the same LUT port configuration even
+    // when the actual global net names are different.
+    dict<IdString, int32_t> netMap;
+    for (CellInfo *cellInfo : lutCells) {
+
+        NPNR_ASSERT(key.numCells < SiteLutMappingKey::MAX_LUT_CELLS);
+        auto &cell = key.cells[key.numCells++];
+
+        cell.type = cellInfo->type;
+        cell.belIndex = cellInfo->bel.index;
+
+        cell.conns.fill(0);
+
+        size_t portId = 0;
+        for (const auto &port : cellInfo->ports) {
+            const auto &portInfo = port.second;
+
+            // Consider only LUT inputs
+            if (portInfo.type != PORT_IN) {
+                continue;
+            }
+
+            // Assign net id if any
+            int32_t netId = 0;
+            if (portInfo.net != nullptr) {
+                auto netInfo = portInfo.net;
+
+                auto it = netMap.find(netInfo->name);
+                if (it != netMap.end()) {
+                    netId = it->second;
+                } else {
+                    netId = (int32_t)netMap.size() + 1;
+                    netMap[netInfo->name] = netId;
+                }
+            }
+
+            NPNR_ASSERT(portId < SiteLutMappingKey::MAX_LUT_INPUTS);
+            cell.conns[portId++] = netId;
+        }
+    }
+
+    // Compute hash
+    key.computeHash();
+
+    return key;
+}
+
+// ============================================================================
+
+bool SiteLutMappingResult::apply(const SiteInformation &siteInfo)
+{
+
+    Context *ctx = const_cast<Context *>(siteInfo.ctx);
+    TileStatus &tileStatus = ctx->get_tile_status(siteInfo.tile);
+
+    for (auto &cell : cells) {
+
+        // Get the bound cell
+        CellInfo *cellInfo = tileStatus.boundcells[cell.belIndex];
+        NPNR_ASSERT(cellInfo);
+
+        // Double check BEL binding
+        NPNR_ASSERT(cellInfo->bel.tile == siteInfo.tile);
+        NPNR_ASSERT(cellInfo->bel.index == cell.belIndex);
+
+        // Cell <-> BEL pin map
+        size_t numPins = cellInfo->lut_cell.pins.size();
+        for (size_t pinIdx = 0; pinIdx < numPins; ++pinIdx) {
+            const IdString &cellPin = cellInfo->lut_cell.pins[pinIdx];
+            auto &belPins = cellInfo->cell_bel_pins[cellPin];
+
+            // There is only one pin
+            belPins.resize(1);
+            belPins[0] = cell.belPins[cellPin];
+        }
+
+        // LUT data
+        // FIXME: Is there any other info that is being updated than vcc_pins ?
+        cellInfo->lut_cell.vcc_pins = std::move(cell.lutCell.vcc_pins);
+    }
+
+    return true;
+}
+
+size_t SiteLutMappingResult::getSizeInBytes() const
+{
+
+    size_t size = 0;
+
+    size += sizeof(SiteLutMappingResult);
+    size += blockedWires.size() * sizeof(std::pair<IdString, IdString>);
+
+    for (const auto &cell : cells) {
+        size += sizeof(Cell);
+        size += cell.belPins.size() * sizeof(decltype(cell.belPins)::value_type);
+    }
+
+    return size;
+}
+
+// ============================================================================
+
+void SiteLutMappingCache::add(const SiteLutMappingKey &key, const SiteLutMappingResult &result)
+{
+    cache_[key] = result;
+}
+
+bool SiteLutMappingCache::get(const SiteLutMappingKey &key, SiteLutMappingResult *result)
+{
+    if (cache_.count(key) == 0) {
+        numMisses++;
+        return false;
+    }
+
+    numHits++;
+    *result = cache_[key];
+    return true;
+}
+
+void SiteLutMappingCache::clear()
+{
+    cache_.clear();
+    clearStats();
+}
+
+void SiteLutMappingCache::clearStats()
+{
+    numHits = 0;
+    numMisses = 0;
+}
+
+// ============================================================================
+
+NEXTPNR_NAMESPACE_END
diff --git a/fpga_interchange/site_lut_mapping_cache.h b/fpga_interchange/site_lut_mapping_cache.h
new file mode 100644
index 00000000..7b1d60a4
--- /dev/null
+++ b/fpga_interchange/site_lut_mapping_cache.h
@@ -0,0 +1,185 @@
+/*
+ *  nextpnr -- Next Generation Place and Route
+ *
+ *  Copyright (C) 2021  Symbiflow Authors
+ *
+ *  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.
+ *
+ */
+
+#ifndef SITE_LUT_MAPPING_CACHE_H
+#define SITE_LUT_MAPPING_CACHE_H
+
+#include "idstring.h"
+#include "nextpnr_namespaces.h"
+#include "site_arch.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+// Key structure used in site LUT mapping cache
+struct SiteLutMappingKey
+{
+
+    // Maximum number of LUT cells per site
+    static constexpr size_t MAX_LUT_CELLS = 8;
+    // Maximum number of LUT inputs per cell
+    static constexpr size_t MAX_LUT_INPUTS = 6;
+
+    // LUT Cell data
+    struct Cell
+    {
+        IdString type;    // Cell type
+        int32_t belIndex; // Bound BEL index
+
+        // Port to net assignments. These are local net ids generated during
+        // key creation. This is to abstract connections from actual design
+        // net names. the Id 0 means unconnected.
+        std::array<int32_t, MAX_LUT_INPUTS> conns;
+
+        bool operator==(const Cell &other) const
+        {
+            return (type == other.type) && (belIndex == other.belIndex) && (conns == other.conns);
+        }
+
+        bool operator!=(const Cell &other) const
+        {
+            return (type != other.type) || (belIndex != other.belIndex) || (conns != other.conns);
+        }
+    };
+
+    int32_t tileType;                      // Tile type
+    int32_t siteType;                      // Site type in that tile type
+    size_t numCells;                       // LUT cell count
+    std::array<Cell, MAX_LUT_CELLS> cells; // LUT cell data
+
+    unsigned int hash_; // Precomputed hash
+
+    // Creates a key from the given site state
+    static SiteLutMappingKey create(const SiteInformation &siteInfo);
+
+    // Returns size in bytes of the key
+    size_t getSizeInBytes() const { return sizeof(SiteLutMappingKey); }
+
+    // Precomputes hash of the key and stores it within
+    void computeHash()
+    {
+        hash_ = mkhash(0, tileType);
+        hash_ = mkhash(hash_, siteType);
+        hash_ = mkhash(hash_, numCells);
+        for (size_t j = 0; j < numCells; ++j) {
+            const auto &cell = cells[j];
+            hash_ = mkhash(hash_, cell.type.index);
+            hash_ = mkhash(hash_, cell.belIndex);
+            for (size_t i = 0; i < MAX_LUT_INPUTS; ++i) {
+                hash_ = mkhash(hash_, cell.conns[i]);
+            }
+        }
+    }
+
+    // Compares cell data of this and other key
+    bool compareCells(const SiteLutMappingKey &other) const
+    {
+        if (numCells != other.numCells) {
+            return false;
+        }
+
+        for (size_t i = 0; i < numCells; ++i) {
+            if (cells[i] != other.cells[i]) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    bool operator==(const SiteLutMappingKey &other) const
+    {
+        return (hash_ == other.hash_) && (tileType == other.tileType) && (siteType == other.siteType) &&
+               compareCells(other);
+    }
+
+    bool operator!=(const SiteLutMappingKey &other) const
+    {
+        return (hash_ != other.hash_) || (tileType != other.tileType) || (siteType != other.siteType) ||
+               !compareCells(other);
+    }
+
+    unsigned int hash() const { return hash_; }
+};
+
+// Site LUT mapping result data
+struct SiteLutMappingResult
+{
+
+    // LUT cell data
+    struct Cell
+    {
+        int32_t belIndex;                 // BEL in tile index
+        LutCell lutCell;                  // LUT mapping data
+        dict<IdString, IdString> belPins; // Cell to BEL pin mapping
+    };
+
+    bool isValid;            // Validity flag
+    std::vector<Cell> cells; // Cell data
+
+    pool<std::pair<IdString, IdString>> blockedWires; // Set of blocked wires
+
+    // Applies the mapping result to the site
+    bool apply(const SiteInformation &siteInfo);
+
+    // Returns size in bytes
+    size_t getSizeInBytes() const;
+};
+
+// Site LUT mapping cache object
+class SiteLutMappingCache
+{
+  public:
+    // Adds an entry to the cache
+    void add(const SiteLutMappingKey &key, const SiteLutMappingResult &result);
+    // Retrieves an entry from the cache. Returns false if not found
+    bool get(const SiteLutMappingKey &key, SiteLutMappingResult *result);
+
+    // Clears the cache
+    void clear();
+    // Clears statistics counters of the cache
+    void clearStats();
+
+    // Return get() miss ratio
+    float getMissRatio() const { return (float)numMisses / (float)(numHits + numMisses); }
+
+    // Returns count of entries in the cache
+    size_t getCount() const { return cache_.size(); }
+
+    // Returns size of the cache rounded upwards to full MBs.
+    size_t getSizeMB() const
+    {
+        size_t size = 0;
+        for (const auto &it : cache_) {
+            size += it.first.getSizeInBytes();
+            size += it.second.getSizeInBytes();
+        }
+
+        const size_t MB = 1024L * 1024L;
+        return (size + MB - 1) / MB; // Round up to megabytes
+    }
+
+  private:
+    dict<SiteLutMappingKey, SiteLutMappingResult> cache_; // The cache
+
+    size_t numHits = 0;   // Hit count
+    size_t numMisses = 0; // Miss count
+};
+
+NEXTPNR_NAMESPACE_END
+
+#endif /* SITE_LUT_MAPPING_CACHE_H */
diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc
index f209bd8c..947081f4 100644
--- a/fpga_interchange/site_router.cc
+++ b/fpga_interchange/site_router.cc
@@ -1050,42 +1050,71 @@ static void apply_routing(Context *ctx, const SiteArch &site_arch, pool<std::pai
 static bool map_luts_in_site(const SiteInformation &site_info, pool<std::pair<IdString, IdString>> *blocked_wires)
 {
     const Context *ctx = site_info.ctx;
-    const std::vector<LutElement> &lut_elements = ctx->lut_elements.at(site_info.tile_type);
-    std::vector<LutMapper> lut_mappers;
-    lut_mappers.reserve(lut_elements.size());
-    for (size_t i = 0; i < lut_elements.size(); ++i) {
-        lut_mappers.push_back(LutMapper(lut_elements[i]));
-    }
+    bool enable_cache = !ctx->arch_args.disable_lut_mapping_cache;
 
-    for (CellInfo *cell : site_info.cells_in_site) {
-        if (cell->lut_cell.pins.empty()) {
-            continue;
-        }
+    // Create a site LUT mapping key
+    SiteLutMappingKey key = SiteLutMappingKey::create(site_info);
 
-        BelId bel = cell->bel;
-        const auto &bel_data = bel_info(ctx->chip_info, bel);
-        if (bel_data.lut_element != -1) {
-            lut_mappers[bel_data.lut_element].cells.push_back(cell);
+    // Get the solution from cache. If not found then compute it
+    SiteLutMappingResult lutMapping;
+    if (!enable_cache || !ctx->site_lut_mapping_cache.get(key, &lutMapping)) {
+
+        const std::vector<LutElement> &lut_elements = ctx->lut_elements.at(site_info.tile_type);
+        std::vector<LutMapper> lut_mappers;
+        lut_mappers.reserve(lut_elements.size());
+        for (size_t i = 0; i < lut_elements.size(); ++i) {
+            lut_mappers.push_back(LutMapper(lut_elements[i]));
         }
-    }
 
-    blocked_wires->clear();
-    for (LutMapper lut_mapper : lut_mappers) {
-        if (lut_mapper.cells.empty()) {
-            continue;
+        for (CellInfo *cell : site_info.cells_in_site) {
+            if (cell->lut_cell.pins.empty()) {
+                continue;
+            }
+
+            BelId bel = cell->bel;
+            const auto &bel_data = bel_info(ctx->chip_info, bel);
+            if (bel_data.lut_element != -1) {
+                lut_mappers[bel_data.lut_element].cells.push_back(cell);
+            }
         }
 
-        pool<const LutBel *, hash_ptr_ops> blocked_luts;
-        if (!lut_mapper.remap_luts(ctx, &blocked_luts)) {
-            return false;
+        bool res = true;
+
+        lutMapping.blockedWires.clear();
+        for (LutMapper lut_mapper : lut_mappers) {
+            if (lut_mapper.cells.empty()) {
+                continue;
+            }
+
+            pool<const LutBel *, hash_ptr_ops> blocked_luts;
+            if (!lut_mapper.remap_luts(ctx, &lutMapping, &blocked_luts)) {
+                res = false;
+                break;
+            }
+
+            for (const LutBel *lut_bel : blocked_luts) {
+                lutMapping.blockedWires.emplace(std::make_pair(lut_bel->name, lut_bel->output_pin));
+            }
         }
 
-        for (const LutBel *lut_bel : blocked_luts) {
-            blocked_wires->emplace(std::make_pair(lut_bel->name, lut_bel->output_pin));
+        lutMapping.isValid = res;
+
+        // Add the solution to the cache
+        if (enable_cache) {
+            ctx->site_lut_mapping_cache.add(key, lutMapping);
         }
     }
 
-    return true;
+    // Apply the solution if valid
+    if (lutMapping.isValid) {
+
+        lutMapping.apply(site_info);
+
+        blocked_wires->clear();
+        blocked_wires->insert(lutMapping.blockedWires.begin(), lutMapping.blockedWires.end());
+    }
+
+    return lutMapping.isValid;
 }
 
 // Block outputs of unavailable LUTs to prevent site router from using them.
@@ -1255,6 +1284,7 @@ bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_sta
     // Because site routing checks are expensive, cache them.
     // SiteRouter::bindBel/unbindBel should correctly invalid the cache by
     // setting dirty=true.
+
     if (!dirty) {
         return site_ok;
     }