333 lines · cpp
1//===- SetTheory.cpp - Generate ordered sets from DAG expressions ---------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the SetTheory class that computes ordered sets of10// Records from DAG expressions.11//12//===----------------------------------------------------------------------===//13 14#include "llvm/TableGen/SetTheory.h"15#include "llvm/ADT/ArrayRef.h"16#include "llvm/ADT/STLExtras.h"17#include "llvm/ADT/SmallVector.h"18#include "llvm/ADT/StringRef.h"19#include "llvm/Support/Casting.h"20#include "llvm/Support/Format.h"21#include "llvm/Support/SMLoc.h"22#include "llvm/Support/raw_ostream.h"23#include "llvm/TableGen/Error.h"24#include "llvm/TableGen/Record.h"25#include <algorithm>26#include <cstdint>27#include <string>28#include <utility>29 30using namespace llvm;31 32// Define the standard operators.33namespace {34 35using RecSet = SetTheory::RecSet;36using RecVec = SetTheory::RecVec;37 38// (add a, b, ...) Evaluate and union all arguments.39struct AddOp : public SetTheory::Operator {40 void apply(SetTheory &ST, const DagInit *Expr, RecSet &Elts,41 ArrayRef<SMLoc> Loc) override {42 ST.evaluate(Expr->arg_begin(), Expr->arg_end(), Elts, Loc);43 }44};45 46// (sub Add, Sub, ...) Set difference.47struct SubOp : public SetTheory::Operator {48 void apply(SetTheory &ST, const DagInit *Expr, RecSet &Elts,49 ArrayRef<SMLoc> Loc) override {50 if (Expr->arg_size() < 2)51 PrintFatalError(Loc, "Set difference needs at least two arguments: " +52 Expr->getAsString());53 RecSet Add, Sub;54 ST.evaluate(*Expr->arg_begin(), Add, Loc);55 ST.evaluate(Expr->arg_begin() + 1, Expr->arg_end(), Sub, Loc);56 for (const auto &I : Add)57 if (!Sub.count(I))58 Elts.insert(I);59 }60};61 62// (and S1, S2) Set intersection.63struct AndOp : public SetTheory::Operator {64 void apply(SetTheory &ST, const DagInit *Expr, RecSet &Elts,65 ArrayRef<SMLoc> Loc) override {66 if (Expr->arg_size() != 2)67 PrintFatalError(Loc, "Set intersection requires two arguments: " +68 Expr->getAsString());69 RecSet S1, S2;70 ST.evaluate(Expr->arg_begin()[0], S1, Loc);71 ST.evaluate(Expr->arg_begin()[1], S2, Loc);72 for (const auto &I : S1)73 if (S2.count(I))74 Elts.insert(I);75 }76};77 78// SetIntBinOp - Abstract base class for (Op S, N) operators.79struct SetIntBinOp : public SetTheory::Operator {80 virtual void apply2(SetTheory &ST, const DagInit *Expr, RecSet &Set,81 int64_t N, RecSet &Elts, ArrayRef<SMLoc> Loc) = 0;82 83 void apply(SetTheory &ST, const DagInit *Expr, RecSet &Elts,84 ArrayRef<SMLoc> Loc) override {85 if (Expr->arg_size() != 2)86 PrintFatalError(Loc, "Operator requires (Op Set, Int) arguments: " +87 Expr->getAsString());88 RecSet Set;89 ST.evaluate(Expr->arg_begin()[0], Set, Loc);90 const auto *II = dyn_cast<IntInit>(Expr->arg_begin()[1]);91 if (!II)92 PrintFatalError(Loc, "Second argument must be an integer: " +93 Expr->getAsString());94 apply2(ST, Expr, Set, II->getValue(), Elts, Loc);95 }96};97 98// (shl S, N) Shift left, remove the first N elements.99struct ShlOp : public SetIntBinOp {100 void apply2(SetTheory &ST, const DagInit *Expr, RecSet &Set, int64_t N,101 RecSet &Elts, ArrayRef<SMLoc> Loc) override {102 if (N < 0)103 PrintFatalError(Loc, "Positive shift required: " +104 Expr->getAsString());105 if (unsigned(N) < Set.size())106 Elts.insert(Set.begin() + N, Set.end());107 }108};109 110// (trunc S, N) Truncate after the first N elements.111struct TruncOp : public SetIntBinOp {112 void apply2(SetTheory &ST, const DagInit *Expr, RecSet &Set, int64_t N,113 RecSet &Elts, ArrayRef<SMLoc> Loc) override {114 if (N < 0)115 PrintFatalError(Loc, "Positive length required: " +116 Expr->getAsString());117 if (unsigned(N) > Set.size())118 N = Set.size();119 Elts.insert(Set.begin(), Set.begin() + N);120 }121};122 123// Left/right rotation.124struct RotOp : public SetIntBinOp {125 const bool Reverse;126 127 RotOp(bool Rev) : Reverse(Rev) {}128 129 void apply2(SetTheory &ST, const DagInit *Expr, RecSet &Set, int64_t N,130 RecSet &Elts, ArrayRef<SMLoc> Loc) override {131 if (Reverse)132 N = -N;133 // N > 0 -> rotate left, N < 0 -> rotate right.134 if (Set.empty())135 return;136 if (N < 0)137 N = Set.size() - (-N % Set.size());138 else139 N %= Set.size();140 Elts.insert(Set.begin() + N, Set.end());141 Elts.insert(Set.begin(), Set.begin() + N);142 }143};144 145// (decimate S, N) Pick every N'th element of S.146struct DecimateOp : public SetIntBinOp {147 void apply2(SetTheory &ST, const DagInit *Expr, RecSet &Set, int64_t N,148 RecSet &Elts, ArrayRef<SMLoc> Loc) override {149 if (N <= 0)150 PrintFatalError(Loc, "Positive stride required: " +151 Expr->getAsString());152 for (unsigned I = 0; I < Set.size(); I += N)153 Elts.insert(Set[I]);154 }155};156 157// (interleave S1, S2, ...) Interleave elements of the arguments.158struct InterleaveOp : public SetTheory::Operator {159 void apply(SetTheory &ST, const DagInit *Expr, RecSet &Elts,160 ArrayRef<SMLoc> Loc) override {161 // Evaluate the arguments individually.162 SmallVector<RecSet, 4> Values(Expr->getNumArgs());163 unsigned MaxSize = 0;164 for (auto [Arg, Value] : zip(Expr->getArgs(), Values)) {165 ST.evaluate(Arg, Value, Loc);166 MaxSize = std::max(MaxSize, unsigned(Value.size()));167 }168 // Interleave arguments into Elts.169 for (unsigned n = 0; n != MaxSize; ++n)170 for (const RecSet &Value : Values)171 if (n < Value.size())172 Elts.insert(Value[n]);173 }174};175 176// (sequence "Format", From, To) Generate a sequence of records by name.177struct SequenceOp : public SetTheory::Operator {178 void apply(SetTheory &ST, const DagInit *Expr, RecSet &Elts,179 ArrayRef<SMLoc> Loc) override {180 int Step = 1;181 if (Expr->arg_size() > 4)182 PrintFatalError(Loc, "Bad args to (sequence \"Format\", From, To): " +183 Expr->getAsString());184 if (Expr->arg_size() == 4) {185 if (const auto *II = dyn_cast<IntInit>(Expr->arg_begin()[3]))186 Step = II->getValue();187 else188 PrintFatalError(Loc, "Stride must be an integer: " +189 Expr->getAsString());190 }191 192 std::string Format;193 if (const auto *SI = dyn_cast<StringInit>(Expr->arg_begin()[0]))194 Format = SI->getValue().str();195 else196 PrintFatalError(Loc, "Format must be a string: " + Expr->getAsString());197 198 int64_t From, To;199 if (const auto *II = dyn_cast<IntInit>(Expr->arg_begin()[1]))200 From = II->getValue();201 else202 PrintFatalError(Loc, "From must be an integer: " + Expr->getAsString());203 if (From < 0 || From >= (1 << 30))204 PrintFatalError(Loc, "From out of range");205 206 if (const auto *II = dyn_cast<IntInit>(Expr->arg_begin()[2]))207 To = II->getValue();208 else209 PrintFatalError(Loc, "To must be an integer: " + Expr->getAsString());210 if (To < 0 || To >= (1 << 30))211 PrintFatalError(Loc, "To out of range");212 213 const RecordKeeper &Records =214 cast<DefInit>(Expr->getOperator())->getDef()->getRecords();215 216 Step *= From <= To ? 1 : -1;217 while (true) {218 if (Step > 0 && From > To)219 break;220 else if (Step < 0 && From < To)221 break;222 std::string Name;223 raw_string_ostream OS(Name);224 OS << format(Format.c_str(), unsigned(From));225 const Record *Rec = Records.getDef(Name);226 if (!Rec)227 PrintFatalError(Loc, "No def named '" + Name + "': " +228 Expr->getAsString());229 // Try to reevaluate Rec in case it is a set.230 if (const RecVec *Result = ST.expand(Rec))231 Elts.insert_range(*Result);232 else233 Elts.insert(Rec);234 235 From += Step;236 }237 }238};239 240// Expand a Def into a set by evaluating one of its fields.241struct FieldExpander : public SetTheory::Expander {242 StringRef FieldName;243 244 FieldExpander(StringRef fn) : FieldName(fn) {}245 246 void expand(SetTheory &ST, const Record *Def, RecSet &Elts) override {247 ST.evaluate(Def->getValueInit(FieldName), Elts, Def->getLoc());248 }249};250 251} // end anonymous namespace252 253// Pin the vtables to this file.254void SetTheory::Operator::anchor() {}255void SetTheory::Expander::anchor() {}256 257SetTheory::SetTheory() {258 addOperator("add", std::make_unique<AddOp>());259 addOperator("sub", std::make_unique<SubOp>());260 addOperator("and", std::make_unique<AndOp>());261 addOperator("shl", std::make_unique<ShlOp>());262 addOperator("trunc", std::make_unique<TruncOp>());263 addOperator("rotl", std::make_unique<RotOp>(false));264 addOperator("rotr", std::make_unique<RotOp>(true));265 addOperator("decimate", std::make_unique<DecimateOp>());266 addOperator("interleave", std::make_unique<InterleaveOp>());267 addOperator("sequence", std::make_unique<SequenceOp>());268}269 270void SetTheory::addOperator(StringRef Name, std::unique_ptr<Operator> Op) {271 Operators[Name] = std::move(Op);272}273 274void SetTheory::addExpander(StringRef ClassName, std::unique_ptr<Expander> E) {275 Expanders[ClassName] = std::move(E);276}277 278void SetTheory::addFieldExpander(StringRef ClassName, StringRef FieldName) {279 addExpander(ClassName, std::make_unique<FieldExpander>(FieldName));280}281 282void SetTheory::evaluate(const Init *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc) {283 // A def in a list can be a just an element, or it may expand.284 if (const auto *Def = dyn_cast<DefInit>(Expr)) {285 if (const RecVec *Result = expand(Def->getDef()))286 return Elts.insert_range(*Result);287 Elts.insert(Def->getDef());288 return;289 }290 291 // Lists simply expand.292 if (const auto *LI = dyn_cast<ListInit>(Expr))293 return evaluate(LI->begin(), LI->end(), Elts, Loc);294 295 // Anything else must be a DAG.296 const auto *DagExpr = dyn_cast<DagInit>(Expr);297 if (!DagExpr)298 PrintFatalError(Loc, "Invalid set element: " + Expr->getAsString());299 const auto *OpInit = dyn_cast<DefInit>(DagExpr->getOperator());300 if (!OpInit)301 PrintFatalError(Loc, "Bad set expression: " + Expr->getAsString());302 auto I = Operators.find(OpInit->getDef()->getName());303 if (I == Operators.end())304 PrintFatalError(Loc, "Unknown set operator: " + Expr->getAsString());305 I->second->apply(*this, DagExpr, Elts, Loc);306}307 308const RecVec *SetTheory::expand(const Record *Set) {309 // Check existing entries for Set and return early.310 ExpandMap::iterator I = Expansions.find(Set);311 if (I != Expansions.end())312 return &I->second;313 314 // This is the first time we see Set. Find a suitable expander.315 for (const Record *SuperClass : Set->getSuperClasses()) {316 // Skip unnamed superclasses.317 if (!isa<StringInit>(SuperClass->getNameInit()))318 continue;319 auto I = Expanders.find(SuperClass->getName());320 if (I == Expanders.end())321 continue;322 // This breaks recursive definitions.323 RecVec &EltVec = Expansions[Set];324 RecSet Elts;325 I->second->expand(*this, Set, Elts);326 EltVec.assign(Elts.begin(), Elts.end());327 return &EltVec;328 }329 330 // Set is not expandable.331 return nullptr;332}333