lib/TableGen/SetTheory.cpp

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