Initial LUT rotation logic.

Signed-off-by: Keith Rothman <537074+litghost@users.noreply.github.com>

8 files changed, 741 insertions, 7 deletions

diff --git a/common/dynamic_bitarray.h b/common/dynamic_bitarray.h
index 10a85fbc..2b5ab2bc 100644
--- a/common/dynamic_bitarray.h
+++ b/common/dynamic_bitarray.h
@@ -70,6 +70,8 @@ template <typename Storage = std::vector<uint8_t>> class DynamicBitarray
 
     size_t size() const { return storage.size() * bits_per_value(); }
 
+    void clear() { return storage.clear(); }
+
   private:
     Storage storage;
 };
diff --git a/fpga_interchange/arch.cc b/fpga_interchange/arch.cc
index dc99f1cd..3b603e5e 100644
--- a/fpga_interchange/arch.cc
+++ b/fpga_interchange/arch.cc
@@ -158,6 +158,7 @@ Arch::Arch(ArchArgs args) : args(args)
 
     int tile_type_index = 0;
     size_t max_tag_count = 0;
+
     for (const TileTypeInfoPOD &tile_type : chip_info->tile_types) {
         max_tag_count = std::max(max_tag_count, tile_type.tags.size());
 
@@ -192,6 +193,50 @@ Arch::Arch(ArchArgs args) : args(args)
         }
     }
 
+    // Initially LutElement vectors for each tile type.
+    tile_type_index = 0;
+    lut_elements.resize(chip_info->tile_types.size());
+    for (const TileTypeInfoPOD &tile_type : chip_info->tile_types) {
+        std::vector<LutElement> &elements = lut_elements[tile_type_index++];
+        elements.reserve(tile_type.lut_elements.size());
+        for (auto &lut_element : tile_type.lut_elements) {
+            elements.emplace_back();
+
+            LutElement &element = elements.back();
+            element.width = lut_element.width;
+            for (auto &lut_bel : lut_element.lut_bels) {
+                auto result = element.lut_bels.emplace(IdString(lut_bel.name), LutBel());
+                NPNR_ASSERT(result.second);
+                LutBel &lut = result.first->second;
+
+                lut.low_bit = lut_bel.low_bit;
+                lut.high_bit = lut_bel.high_bit;
+
+                lut.pins.reserve(lut_bel.pins.size());
+                for (size_t i = 0; i < lut_bel.pins.size(); ++i) {
+                    IdString pin(lut_bel.pins[i]);
+                    lut.pins.push_back(pin);
+                    lut.pin_to_index[pin] = i;
+                }
+            }
+
+            element.compute_pin_order();
+        }
+    }
+
+    // Map lut cell types to their LutCellPOD
+    for (const LutCellPOD &lut_cell : chip_info->cell_map->lut_cells) {
+        IdString cell_type(lut_cell.cell);
+        auto result = lut_cells.emplace(cell_type, &lut_cell);
+        NPNR_ASSERT(result.second);
+    }
+
+    raw_bin_constant = std::regex("[01]+", std::regex_constants::ECMAScript | std::regex_constants::optimize);
+    verilog_bin_constant =
+            std::regex("([0-9]+)'b([01]+)", std::regex_constants::ECMAScript | std::regex_constants::optimize);
+    verilog_hex_constant =
+            std::regex("([0-9]+)'h([0-9a-fA-F]+)", std::regex_constants::ECMAScript | std::regex_constants::optimize);
+
     default_tags.resize(max_tag_count);
 }
 
@@ -603,6 +648,7 @@ bool Arch::getBudgetOverride(const NetInfo *net_info, const PortRef &sink, delay
 
 bool Arch::pack()
 {
+    decode_lut_cells();
     merge_constant_nets();
     pack_ports();
     return true;
@@ -666,11 +712,71 @@ bool Arch::route()
     } else {
         log_error("FPGA interchange architecture does not support router '%s'\n", router.c_str());
     }
+
+    if (result) {
+        result = route_vcc_to_unused_lut_pins();
+    }
+
     getCtx()->attrs[getCtx()->id("step")] = std::string("route");
     archInfoToAttributes();
+
     return result;
 }
 
+bool Arch::route_vcc_to_unused_lut_pins() {
+    std::string router = str_or_default(settings, id("router"), defaultRouter);
+
+    // Fixup LUT vcc pins.
+    IdString vcc_net_name(chip_info->constants->vcc_net_name);
+    for (BelId bel : getBels()) {
+        CellInfo *cell = getBoundBelCell(bel);
+        if (cell == nullptr) {
+            continue;
+        }
+
+        if (cell->lut_cell.vcc_pins.empty()) {
+            continue;
+        }
+
+        for (auto bel_pin : cell->lut_cell.vcc_pins) {
+            PortInfo port_info;
+            port_info.name = bel_pin;
+            port_info.type = PORT_IN;
+            port_info.net = nullptr;
+
+            WireId lut_pin_wire = getBelPinWire(bel, bel_pin);
+            auto iter = wire_to_net.find(lut_pin_wire);
+            if (iter != wire_to_net.end()) {
+                if (iter->second != nullptr) {
+                    // This pin is now used by a route through.
+                    continue;
+                }
+            }
+
+            auto result = cell->ports.emplace(bel_pin, port_info);
+            if (result.second) {
+                cell->cell_bel_pins[bel_pin].push_back(bel_pin);
+                connectPort(vcc_net_name, cell->name, bel_pin);
+                cell->const_ports.emplace(bel_pin);
+            } else {
+                NPNR_ASSERT(result.first->second.net == getNetByAlias(vcc_net_name));
+                auto result2 = cell->cell_bel_pins.emplace(bel_pin, std::vector<IdString>({bel_pin}));
+                NPNR_ASSERT(result2.first->second.at(0) == bel_pin);
+                NPNR_ASSERT(result2.first->second.size() == 1);
+            }
+        }
+    }
+
+    if (router == "router1") {
+        return router1(getCtx(), Router1Cfg(getCtx()));
+    } else if (router == "router2") {
+        router2(getCtx(), Router2Cfg(getCtx()));
+        return true;
+    } else {
+        log_error("FPGA interchange architecture does not support router '%s'\n", router.c_str());
+    }
+}
+
 // -----------------------------------------------------------------------
 
 std::vector<GraphicElement> Arch::getDecalGraphics(DecalId decal) const { return {}; }
@@ -791,7 +897,20 @@ const std::vector<std::string> Arch::availableRouters = {"router1", "router2"};
 void Arch::map_cell_pins(CellInfo *cell, int32_t mapping, bool bind_constants)
 {
     cell->cell_mapping = mapping;
-    cell->cell_bel_pins.clear();
+    if (cell->lut_cell.pins.empty()) {
+        cell->cell_bel_pins.clear();
+    } else {
+        std::vector<IdString> cell_pin_to_remove;
+        for (auto port_pair : cell->cell_bel_pins) {
+            if (!cell->lut_cell.lut_pins.count(port_pair.first)) {
+                cell_pin_to_remove.push_back(port_pair.first);
+            }
+        }
+
+        for (IdString cell_pin : cell_pin_to_remove) {
+            NPNR_ASSERT(cell->cell_bel_pins.erase(cell_pin));
+        }
+    }
     for (IdString const_port : cell->const_ports) {
         NPNR_ASSERT(cell->ports.erase(const_port));
     }
@@ -805,6 +924,11 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping, bool bind_constants)
         IdString cell_pin(pin_map.cell_pin);
         IdString bel_pin(pin_map.bel_pin);
 
+        // Skip assigned LUT pins, as they are already mapped!
+        if (cell->lut_cell.lut_pins.count(cell_pin) && cell->cell_bel_pins.count(cell_pin)) {
+            continue;
+        }
+
         if (cell_pin.str(this) == "GND") {
             if (bind_constants) {
                 PortInfo port_info;
@@ -869,11 +993,17 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping, bool bind_constants)
             IdString cell_pin(pin_map.cell_pin);
             IdString bel_pin(pin_map.bel_pin);
 
+            // Skip assigned LUT pins, as they are already mapped!
+            if (cell->lut_cell.lut_pins.count(cell_pin) && cell->cell_bel_pins.count(cell_pin)) {
+                continue;
+            }
+
             if (cell_pin.str(this) == "GND") {
                 if (bind_constants) {
                     PortInfo port_info;
                     port_info.name = bel_pin;
                     port_info.type = PORT_IN;
+                    port_info.net = nullptr;
 
                     auto result = cell->ports.emplace(bel_pin, port_info);
                     if (result.second) {
@@ -895,6 +1025,7 @@ void Arch::map_cell_pins(CellInfo *cell, int32_t mapping, bool bind_constants)
                     PortInfo port_info;
                     port_info.name = bel_pin;
                     port_info.type = PORT_IN;
+                    port_info.net = nullptr;
 
                     auto result = cell->ports.emplace(bel_pin, port_info);
                     if (result.second) {
@@ -1135,6 +1266,70 @@ void Arch::report_invalid_bel(BelId bel, CellInfo *cell) const
               nameOfBel(bel), mapping);
 }
 
+void Arch::read_lut_equation(nextpnr::DynamicBitarray<> *equation, const Property &equation_parameter) const
+{
+    equation->fill(false);
+    std::string eq_str = equation_parameter.as_string();
+    std::smatch results;
+    if (std::regex_match(eq_str, results, raw_bin_constant)) {
+        size_t bit_idx = 0;
+        const std::string &bits = results[0];
+        NPNR_ASSERT(bits.size() <= equation->size());
+        for (auto bit = bits.rbegin(); bit != bits.rend(); ++bit) {
+            if (*bit == '0') {
+                equation->set(bit_idx++, false);
+            } else {
+                NPNR_ASSERT(*bit == '1');
+                equation->set(bit_idx++, true);
+            }
+        }
+    } else if (std::regex_match(eq_str, results, verilog_bin_constant)) {
+        int iwidth = std::stoi(results[1]);
+        NPNR_ASSERT(iwidth >= 0);
+        size_t width = iwidth;
+        std::string bits = results[2];
+        NPNR_ASSERT(width <= equation->size());
+        NPNR_ASSERT(bits.size() <= width);
+        size_t bit_idx = 0;
+        for (auto bit = bits.rbegin(); bit != bits.rend(); ++bit) {
+            if (*bit == '0') {
+                equation->set(bit_idx++, false);
+            } else {
+                NPNR_ASSERT(*bit == '1');
+                equation->set(bit_idx++, true);
+            }
+        }
+    } else {
+        NPNR_ASSERT(false);
+    }
+}
+
+void Arch::decode_lut_cells()
+{
+    for (auto &cell_pair : cells) {
+        CellInfo *cell = cell_pair.second.get();
+        auto iter = lut_cells.find(cell->type);
+        if (iter == lut_cells.end()) {
+            cell->lut_cell.pins.clear();
+            cell->lut_cell.equation.clear();
+            continue;
+        }
+
+        const LutCellPOD &lut_cell = *iter->second;
+
+        cell->lut_cell.pins.reserve(lut_cell.input_pins.size());
+        for (uint32_t pin : lut_cell.input_pins) {
+            cell->lut_cell.pins.push_back(IdString(pin));
+            cell->lut_cell.lut_pins.emplace(IdString(pin));
+        }
+
+        IdString equation_parameter(lut_cell.parameter);
+        const Property &equation = cell->params.at(equation_parameter);
+        cell->lut_cell.equation.resize(1 << cell->lut_cell.pins.size());
+        read_lut_equation(&cell->lut_cell.equation, equation);
+    }
+}
+
 // Instance constraint templates.
 template void Arch::ArchConstraints::bindBel(Arch::ArchConstraints::TagState *, const Arch::ConstraintRange);
 template void Arch::ArchConstraints::unbindBel(Arch::ArchConstraints::TagState *, const Arch::ConstraintRange);
diff --git a/fpga_interchange/arch.h b/fpga_interchange/arch.h
index 13cab02f..16c79e8a 100644
--- a/fpga_interchange/arch.h
+++ b/fpga_interchange/arch.h
@@ -28,6 +28,7 @@
 
 #include <iostream>
 
+#include <regex>
 #include "constraints.h"
 #include "dedicated_interconnect.h"
 #include "site_router.h"
@@ -69,7 +70,8 @@ NPNR_PACKED_STRUCT(struct BelInfoPOD {
     int16_t site;
     int16_t site_variant; // some sites have alternative types
     int16_t category;
-    int16_t synthetic;
+    int8_t synthetic;
+    int8_t lut_element;
 
     RelPtr<int32_t> pin_map; // Index into CellMapPOD::cell_bel_map
 });
@@ -119,6 +121,18 @@ NPNR_PACKED_STRUCT(struct ConstraintTagPOD {
     RelSlice<int32_t> states; // constid
 });
 
+NPNR_PACKED_STRUCT(struct LutBelPOD {
+    uint32_t name;          // constid
+    RelSlice<int32_t> pins; // constid
+    uint32_t low_bit;
+    uint32_t high_bit;
+});
+
+NPNR_PACKED_STRUCT(struct LutElementPOD {
+    int32_t width;
+    RelSlice<LutBelPOD> lut_bels;
+});
+
 NPNR_PACKED_STRUCT(struct TileTypeInfoPOD {
     int32_t name; // Tile type constid
 
@@ -130,6 +144,8 @@ NPNR_PACKED_STRUCT(struct TileTypeInfoPOD {
 
     RelSlice<ConstraintTagPOD> tags;
 
+    RelSlice<LutElementPOD> lut_elements;
+
     RelSlice<int32_t> site_types; // constid
 });
 
@@ -190,12 +206,20 @@ NPNR_PACKED_STRUCT(struct CellBelMapPOD {
     RelSlice<CellConstraintPOD> constraints;
 });
 
+NPNR_PACKED_STRUCT(struct LutCellPOD {
+    int32_t cell;                 // constid
+    RelSlice<int32_t> input_pins; // constids
+    int32_t parameter;
+});
+
 NPNR_PACKED_STRUCT(struct CellMapPOD {
     // Cell names supported in this arch.
     RelSlice<int32_t> cell_names;       // constids
     RelSlice<int32_t> cell_bel_buckets; // constids
 
     RelSlice<CellBelMapPOD> cell_bel_map;
+
+    RelSlice<LutCellPOD> lut_cells;
 });
 
 NPNR_PACKED_STRUCT(struct PackagePinPOD {
@@ -1362,6 +1386,7 @@ struct Arch : ArchAPI<ArchRanges>
     void place_iobufs(WireId pad_wire, NetInfo *net, const std::unordered_set<CellInfo *> &tightly_attached_bels,
                       std::unordered_set<CellInfo *> *placed_cells);
     void pack_ports();
+    void decode_lut_cells();
     bool pack() override;
     bool place() override;
     bool route() override;
@@ -1706,6 +1731,14 @@ struct Arch : ArchAPI<ArchRanges>
     std::vector<IdString> no_pins;
     IdString gnd_cell_pin;
     IdString vcc_cell_pin;
+    std::vector<std::vector<LutElement>> lut_elements;
+    std::unordered_map<IdString, const LutCellPOD *> lut_cells;
+
+    std::regex raw_bin_constant;
+    std::regex verilog_bin_constant;
+    std::regex verilog_hex_constant;
+    void read_lut_equation(nextpnr::DynamicBitarray<> *equation, const Property &equation_parameter) const;
+    bool route_vcc_to_unused_lut_pins();
 };
 
 NEXTPNR_NAMESPACE_END
diff --git a/fpga_interchange/archdefs.h b/fpga_interchange/archdefs.h
index 33d999bb..e355a6c4 100644
--- a/fpga_interchange/archdefs.h
+++ b/fpga_interchange/archdefs.h
@@ -22,6 +22,8 @@
 #error Include "archdefs.h" via "nextpnr.h" only.
 #endif
 
+#include "luts.h"
+
 NEXTPNR_NAMESPACE_BEGIN
 
 #include <cstdint>
@@ -107,6 +109,7 @@ struct ArchCellInfo
     int32_t cell_mapping;
     std::unordered_map<IdString, std::vector<IdString>> cell_bel_pins;
     std::unordered_set<IdString> const_ports;
+    LutCell lut_cell;
 };
 
 NEXTPNR_NAMESPACE_END
diff --git a/fpga_interchange/luts.cc b/fpga_interchange/luts.cc
new file mode 100644
index 00000000..dc4e0531
--- /dev/null
+++ b/fpga_interchange/luts.cc
@@ -0,0 +1,370 @@
+/*
+ *  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 "nextpnr.h"
+
+#include "luts.h"
+#include "log.h"
+
+NEXTPNR_NAMESPACE_BEGIN
+
+bool rotate_and_merge_lut_equation(std::vector<LogicLevel> * result,
+        const LutBel & lut_bel,
+        const nextpnr::DynamicBitarray<> &old_equation,
+        const std::vector<int32_t> &pin_map,
+        uint32_t used_pins) {
+    // pin_map maps pin indicies from the old pin to the new pin.
+    // So a reversal of a LUT4 would have a pin map of:
+    // pin_map[0] = 3;
+    // pin_map[1] = 2;
+    // pin_map[2] = 1;
+    // pin_map[3] = 0;
+
+    size_t bel_width = 1 << lut_bel.pins.size();
+    for(size_t bel_address = 0; bel_address < bel_width; ++bel_address) {
+        bool address_reachable = true;
+        size_t cell_address = 0;
+        for(size_t bel_pin_idx = 0; bel_pin_idx < lut_bel.pins.size(); ++bel_pin_idx) {
+            // This address line is 0, so don't translate this bit to the cell
+            // address.
+            if((bel_address & (1 << bel_pin_idx)) == 0) {
+                // This pin is unused, so the line will be tied high, this
+                // address is unreachable.
+                if((used_pins & (1 << bel_pin_idx)) == 0) {
+                    address_reachable = false;
+                    break;
+                }
+
+                continue;
+            }
+
+
+            auto cell_pin_idx = pin_map[bel_pin_idx];
+
+            // Is this BEL pin used for this cell?
+            if(cell_pin_idx < 0) {
+                // This BEL pin is not used for the LUT cell, skip
+                continue;
+            }
+
+            cell_address |= (1 << cell_pin_idx);
+        }
+
+        if(!address_reachable) {
+            continue;
+        }
+
+        bel_address += lut_bel.low_bit;
+        if(old_equation.get(cell_address)) {
+            if((*result)[bel_address] == LL_Zero) {
+                // Output equation has a conflict!
+                return false;
+            }
+
+            (*result)[bel_address] = LL_One;
+        } else {
+            if((*result)[bel_address] == LL_One) {
+                // Output equation has a conflict!
+                return false;
+            }
+            (*result)[bel_address] = LL_Zero;
+        }
+    }
+
+    return true;
+}
+
+static constexpr bool kCheckOutputEquation = true;
+
+struct LutPin {
+    struct LutPinUser {
+        size_t cell_idx;
+        size_t cell_pin_idx;
+    };
+
+    const NetInfo * net = nullptr;
+    std::vector<LutPinUser> users;
+
+    int32_t min_pin = -1;
+    int32_t max_pin = -1;
+
+    void add_user(const LutBel & lut_bel, size_t cell_idx, size_t cell_pin_idx) {
+        if(min_pin < 0) {
+            min_pin = lut_bel.min_pin;
+            max_pin = lut_bel.max_pin;
+        }
+
+        min_pin = std::max(min_pin, lut_bel.min_pin);
+        max_pin = std::min(max_pin, lut_bel.max_pin);
+
+        users.emplace_back();
+        users.back().cell_idx = cell_idx;
+        users.back().cell_pin_idx = cell_pin_idx;
+    }
+
+    bool operator < (const LutPin & other) const {
+        return max_pin < other.max_pin;
+    }
+};
+
+bool LutMapper::remap_luts(const Context *ctx) {
+    std::unordered_map<NetInfo*, LutPin> lut_pin_map;
+    std::vector<const LutBel*> lut_bels;
+    lut_bels.resize(cells.size());
+
+    for(size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
+        const CellInfo * cell = cells[cell_idx];
+#ifdef DEBUG_LUT_ROTATION
+        log_info("Mapping %s %s eq = %s at %s\n", cell->type.c_str(ctx), cell->name.c_str(ctx), cell->params.at(ctx->id("INIT")).c_str(), ctx->nameOfBel(cell->bel));
+#endif
+
+        auto & bel_data = bel_info(ctx->chip_info, cell->bel);
+        IdString bel_name(bel_data.name);
+        auto & lut_bel = element.lut_bels.at(bel_name);
+        lut_bels[cell_idx] = &lut_bel;
+
+        for(size_t pin_idx = 0; pin_idx < cell->lut_cell.pins.size(); ++pin_idx) {
+            IdString lut_pin_name = cell->lut_cell.pins[pin_idx];
+            const PortInfo & port_info = cell->ports.at(lut_pin_name);
+            NPNR_ASSERT(port_info.net != nullptr);
+
+            auto result = lut_pin_map.emplace(port_info.net, LutPin());
+            LutPin & lut_pin = result.first->second;
+            lut_pin.net = port_info.net;
+            lut_pin.add_user(lut_bel, cell_idx, pin_idx);
+        }
+    }
+
+    if(lut_pin_map.size() > element.pins.size()) {
+        // Trival conflict, more nets entering element than pins are
+        // available!
+#ifdef DEBUG_LUT_ROTATION
+        log_info("Trival failure %zu > %zu, %zu %zu\n",
+                lut_pin_map.size(), element.pins.size(), element.width, element.lut_bels.size());
+#endif
+        return false;
+    }
+
+    std::vector<LutPin> lut_pins;
+    lut_pins.reserve(lut_pin_map.size());
+    for(auto lut_pin_pair : lut_pin_map) {
+        lut_pins.push_back(std::move(lut_pin_pair.second));
+    }
+    lut_pin_map.clear();
+    std::sort(lut_pins.begin(), lut_pins.end());
+
+    std::vector<std::vector<size_t>> cell_to_bel_pin_remaps;
+    std::vector<std::vector<int32_t>> bel_to_cell_pin_remaps;
+    cell_to_bel_pin_remaps.resize(cells.size());
+    bel_to_cell_pin_remaps.resize(cells.size());
+    for(size_t i = 0; i < cells.size(); ++i) {
+        cell_to_bel_pin_remaps[i].resize(cells[i]->lut_cell.pins.size());
+        bel_to_cell_pin_remaps[i].resize(lut_bels[i]->pins.size(), -1);
+    }
+
+    uint32_t used_pins = 0;
+    size_t idx = 0;
+    std::vector<IdString> net_pins(lut_pins.size());
+    for(auto &lut_pin : lut_pins) {
+        size_t net_idx = idx++;
+        used_pins |= (1 << net_idx);
+
+        for(auto cell_pin_idx : lut_pin.users) {
+            size_t cell_idx = cell_pin_idx.cell_idx;
+            size_t pin_idx = cell_pin_idx.cell_pin_idx;
+            IdString bel_pin = lut_bels[cell_idx]->pins[net_idx];
+#ifdef DEBUG_LUT_ROTATION
+            log_info("%s %s %s => %s (%s)\n",
+                    cells[cell_idx]->type.c_str(ctx),
+                    cells[cell_idx]->name.c_str(ctx),
+                    cells[cell_idx]->lut_cell.pins[pin_idx].c_str(ctx),
+                    bel_pin.c_str(ctx),
+                    lut_pin.net->name.c_str(ctx));
+#endif
+            if(net_pins[net_idx] == IdString()) {
+                net_pins[net_idx] = bel_pin;
+            } else {
+                NPNR_ASSERT(net_pins[net_idx] == bel_pin);
+            }
+
+            cell_to_bel_pin_remaps[cell_idx][pin_idx] = net_idx;
+            bel_to_cell_pin_remaps[cell_idx][net_idx] = pin_idx;
+        }
+    }
+
+    // Try to see if the equations are mergable!
+    std::vector<LogicLevel> equation_result;
+    equation_result.resize(element.width, LL_DontCare);
+    for(size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
+        const CellInfo * cell = cells[cell_idx];
+        auto & lut_bel = *lut_bels[cell_idx];
+        if(!rotate_and_merge_lut_equation(&equation_result,
+                lut_bel, cell->lut_cell.equation, bel_to_cell_pin_remaps[cell_idx], used_pins)) {
+#ifdef DEBUG_LUT_ROTATION
+            log_info("Failed to find a solution!\n");
+            for(auto *cell : cells) {
+                log_info("%s %s : %s\b\n",
+                        cell->type.c_str(ctx),
+                        cell->name.c_str(ctx),
+                        cell->params.at(ctx->id("INIT")).c_str());
+            }
+#endif
+            return false;
+        }
+    }
+
+#ifdef DEBUG_LUT_ROTATION
+    log_info("Found a solution!\n");
+#endif
+
+    // Sanity check final equation to make sure no assumptions are violated.
+    if(kCheckOutputEquation) {
+        for(size_t cell_idx = 0; cell_idx < cells.size(); ++cell_idx) {
+            CellInfo * cell = cells[cell_idx];
+            auto & lut_bel = *lut_bels[cell_idx];
+
+            std::unordered_map<IdString, IdString> cell_to_bel_map;
+            for(size_t pin_idx = 0; pin_idx < cell->lut_cell.pins.size(); ++pin_idx) {
+                size_t bel_pin_idx = cell_to_bel_pin_remaps[cell_idx][pin_idx];
+                NPNR_ASSERT(bel_pin_idx < lut_bel.pins.size());
+                cell_to_bel_map[cell->lut_cell.pins[pin_idx]] = lut_bel.pins[bel_pin_idx];
+            }
+
+            check_equation(cell->lut_cell, cell_to_bel_map, lut_bel, equation_result, used_pins);
+        }
+    }
+
+    // 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]]);
+        }
+
+        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[bel_pin_idx]);
+            }
+        }
+    }
+
+    return true;
+}
+
+void check_equation(
+        const LutCell & lut_cell,
+        const std::unordered_map<IdString, IdString> &cell_to_bel_map,
+        const LutBel & lut_bel,
+        const std::vector<LogicLevel> &equation,
+        uint32_t used_pins) {
+    std::vector<int8_t> pin_map;
+    pin_map.resize(lut_bel.pins.size(), -1);
+
+    NPNR_ASSERT(lut_cell.pins.size() < std::numeric_limits<decltype(pin_map)::value_type>::max());
+
+    for(size_t cell_pin_idx = 0; cell_pin_idx < lut_cell.pins.size(); ++cell_pin_idx) {
+        IdString cell_pin = lut_cell.pins[cell_pin_idx];
+        IdString bel_pin = cell_to_bel_map.at(cell_pin);
+        size_t bel_pin_idx = lut_bel.pin_to_index.at(bel_pin);
+
+        pin_map[bel_pin_idx] = cell_pin_idx;
+    }
+
+    // Iterate over all BEL addresses in the LUT, and ensure that the original
+    // LUT equation is respected.
+    size_t bel_width = 1 << lut_bel.pins.size();
+    NPNR_ASSERT(lut_bel.low_bit + bel_width == lut_bel.high_bit + 1);
+    for(size_t bel_address = 0; bel_address < bel_width; ++bel_address) {
+        LogicLevel level = equation[bel_address + lut_bel.low_bit];
+
+        bool address_reachable = true;
+        size_t cell_address = 0;
+        for(size_t bel_pin_idx = 0; bel_pin_idx < lut_bel.pins.size(); ++bel_pin_idx) {
+            // This address line is 0, so don't translate this bit to the cell
+            // address.
+            if((bel_address & (1 << bel_pin_idx)) == 0) {
+                // This pin is unused, so the line will be tied high, this
+                // address is unreachable.
+                if((used_pins & (1 << bel_pin_idx)) == 0) {
+                    address_reachable = false;
+                    break;
+                }
+                continue;
+            }
+
+            auto cell_pin_idx = pin_map[bel_pin_idx];
+
+            // Is this BEL pin used for this cell?
+            if(cell_pin_idx < 0) {
+                // This BEL pin is not used for the LUT cell, skip
+                continue;
+            }
+
+            cell_address |= (1 << cell_pin_idx);
+        }
+
+        if(!address_reachable) {
+            continue;
+        }
+
+        if(lut_cell.equation.get(cell_address)) {
+            NPNR_ASSERT(level == LL_One);
+        } else {
+            NPNR_ASSERT(level == LL_Zero);
+        }
+    }
+}
+
+void LutElement::compute_pin_order() {
+    pins.clear();
+    pin_to_index.clear();
+
+    for(auto & lut_bel_pair : lut_bels) {
+        auto & lut_bel = lut_bel_pair.second;
+
+        for(size_t pin_idx = 0; pin_idx < lut_bel.pins.size(); ++pin_idx) {
+            IdString pin = lut_bel.pins[pin_idx];
+            auto result = pin_to_index.emplace(pin, pin_idx);
+            if(!result.second) {
+                // Not sure when this isn't true, but check it for now!
+                NPNR_ASSERT(result.first->second == pin_idx);
+            }
+        }
+    }
+
+    pins.resize(pin_to_index.size());
+    for(auto &pin_pair : pin_to_index) {
+        pins.at(pin_pair.second) = pin_pair.first;
+    }
+
+    for(auto & lut_bel_pair : lut_bels) {
+        auto & lut_bel = lut_bel_pair.second;
+        lut_bel.min_pin = pin_to_index.at(lut_bel.pins.front());
+        lut_bel.max_pin = pin_to_index.at(lut_bel.pins.back());
+    }
+}
+
+NEXTPNR_NAMESPACE_END
diff --git a/fpga_interchange/luts.h b/fpga_interchange/luts.h
new file mode 100644
index 00000000..0218653a
--- /dev/null
+++ b/fpga_interchange/luts.h
@@ -0,0 +1,101 @@
+/*
+ *  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 NEXTPNR_H
+#error Include "luts.h" via "nextpnr.h" only.
+#endif
+
+#include "dynamic_bitarray.h"
+
+#ifndef LUTS_H
+#define LUTS_H
+
+NEXTPNR_NAMESPACE_BEGIN
+
+struct CellInfo;
+struct Context;
+
+enum LogicLevel {
+    LL_Zero,
+    LL_One,
+    LL_DontCare
+};
+
+struct LutCell {
+    // LUT cell pins for equation, LSB first.
+    std::vector<IdString> pins;
+    std::unordered_set<IdString> lut_pins;
+    std::unordered_set<IdString> vcc_pins;
+    nextpnr::DynamicBitarray<> equation;
+};
+
+struct LutBel {
+    // LUT BEL pins to LUT array index.
+    std::vector<IdString> pins;
+    std::unordered_map<IdString, size_t> pin_to_index;
+
+    // What part of the LUT equation does this LUT output use?
+    // This assumes contiguous LUT bits.
+    uint32_t low_bit;
+    uint32_t high_bit;
+
+    int32_t min_pin;
+    int32_t max_pin;
+};
+
+// Work forward from cell definition and cell -> bel pin map and check that 
+// equation is valid.
+void check_equation(
+        const LutCell & lut_cell,
+        const std::unordered_map<IdString, IdString> &cell_to_bel_map,
+        const LutBel & lut_bel,
+        const std::vector<LogicLevel> &equation,
+        uint32_t used_pins);
+
+struct LutElement {
+    size_t width;
+    std::unordered_map<IdString, LutBel> lut_bels;
+
+    void compute_pin_order();
+
+    std::vector<IdString> pins;
+    std::unordered_map<IdString, size_t> pin_to_index;
+};
+
+struct LutMapper {
+    LutMapper(const LutElement & element) : element(element) {}
+    const LutElement & element;
+
+    std::vector<CellInfo*> cells;
+
+    bool remap_luts(const Context *ctx);
+};
+
+// Rotate and merge a LUT equation into an array of levels.
+//
+// If a conflict arises, return false and result is in an indeterminate state.
+bool rotate_and_merge_lut_equation(std::vector<LogicLevel> * result,
+        const LutBel & lut_bel,
+        const nextpnr::DynamicBitarray<> &old_equation,
+        const std::vector<size_t> &pin_map,
+        uint32_t used_pins);
+
+NEXTPNR_NAMESPACE_END
+
+#endif /* LUTS_H */
diff --git a/fpga_interchange/site_router.cc b/fpga_interchange/site_router.cc
index 7232b635..56bce01a 100644
--- a/fpga_interchange/site_router.cc
+++ b/fpga_interchange/site_router.cc
@@ -747,17 +747,42 @@ bool SiteRouter::checkSiteRouting(const Context *ctx, const TileStatus &tile_sta
             return site_ok;
         }
     }
-    //
+
     // FIXME: Populate "consumed_wires" with all VCC/GND tied in the site.
     // This will allow route_site to leverage site local constant sources.
     //
     // FIXME: Handle case where a constant is requested, but use of an
     // inverter is possible. This is the place to handle "bestConstant"
     // (e.g. route VCC's over GND's, etc).
-    //
-    // FIXME: Enable some LUT rotation!
-    // Default cell/bel pin map always uses high pins, which will generate
-    // conflicts where there are none!!!
+    auto tile_type_idx = ctx->chip_info->tiles[tile].type;
+    const std::vector<LutElement> &lut_elements = ctx->lut_elements.at(tile_type_idx);
+    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]));
+    }
+
+    for (CellInfo *cell : 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);
+        }
+    }
+
+    for (LutMapper lut_mapper : lut_mappers) {
+        if (lut_mapper.cells.empty()) {
+            continue;
+        }
+
+        if (!lut_mapper.remap_luts(ctx)) {
+            return false;
+        }
+    }
 
     SiteInformation site_info(ctx, cells_in_site);
 
diff --git a/fpga_interchange/site_router.h b/fpga_interchange/site_router.h
index 561dae9d..6af32747 100644
--- a/fpga_interchange/site_router.h
+++ b/fpga_interchange/site_router.h
@@ -22,6 +22,9 @@
 #error Include "site_router.h" via "nextpnr.h" only.
 #endif
 
+#ifndef SITE_ROUTER_H
+#define SITE_ROUTER_H
+
 NEXTPNR_NAMESPACE_BEGIN
 
 struct Context;
@@ -43,3 +46,5 @@ struct SiteRouter
 };
 
 NEXTPNR_NAMESPACE_END
+
+#endif /* SITE_ROUTER_H */