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