11de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen//===- SetTheory.cpp - Generate ordered sets from DAG expressions ---------===// 21de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 31de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 41de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 51de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 61de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 71de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 81de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 91de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 101de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// This file implements the SetTheory class that computes ordered sets of 111de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// Records from DAG expressions. 121de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 131de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 141de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 151de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#include "SetTheory.h" 164ffd89fa4d2788611187d1a534d2ed46adf1702cChandler Carruth#include "llvm/Support/Format.h" 177c788888872233748da10a8177a9a1eb176c1bc8Peter Collingbourne#include "llvm/TableGen/Error.h" 187c788888872233748da10a8177a9a1eb176c1bc8Peter Collingbourne#include "llvm/TableGen/Record.h" 191de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 201de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenusing namespace llvm; 211de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 221de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// Define the standard operators. 231de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesennamespace { 241de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 251de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesentypedef SetTheory::RecSet RecSet; 261de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesentypedef SetTheory::RecVec RecVec; 271de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 281de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// (add a, b, ...) Evaluate and union all arguments. 291de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenstruct AddOp : public SetTheory::Operator { 302c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger void apply(SetTheory &ST, DagInit *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc) { 312c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger ST.evaluate(Expr->arg_begin(), Expr->arg_end(), Elts, Loc); 321de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 331de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen}; 341de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 351de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// (sub Add, Sub, ...) Set difference. 361de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenstruct SubOp : public SetTheory::Operator { 372c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger void apply(SetTheory &ST, DagInit *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc) { 381de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (Expr->arg_size() < 2) 3961131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Set difference needs at least two arguments: " + 402c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger Expr->getAsString()); 411de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen RecSet Add, Sub; 422c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger ST.evaluate(*Expr->arg_begin(), Add, Loc); 432c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger ST.evaluate(Expr->arg_begin() + 1, Expr->arg_end(), Sub, Loc); 441de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen for (RecSet::iterator I = Add.begin(), E = Add.end(); I != E; ++I) 451de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (!Sub.count(*I)) 461de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Elts.insert(*I); 471de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 481de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen}; 491de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 501de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// (and S1, S2) Set intersection. 511de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenstruct AndOp : public SetTheory::Operator { 522c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger void apply(SetTheory &ST, DagInit *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc) { 531de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (Expr->arg_size() != 2) 5461131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Set intersection requires two arguments: " + 552c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger Expr->getAsString()); 561de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen RecSet S1, S2; 572c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger ST.evaluate(Expr->arg_begin()[0], S1, Loc); 582c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger ST.evaluate(Expr->arg_begin()[1], S2, Loc); 591de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen for (RecSet::iterator I = S1.begin(), E = S1.end(); I != E; ++I) 601de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (S2.count(*I)) 611de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Elts.insert(*I); 621de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 631de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen}; 641de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 651de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// SetIntBinOp - Abstract base class for (Op S, N) operators. 661de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenstruct SetIntBinOp : public SetTheory::Operator { 6705bce0beee87512e52428d4b80f5a8e79a949576David Greene virtual void apply2(SetTheory &ST, DagInit *Expr, 681de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen RecSet &Set, int64_t N, 692c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger RecSet &Elts, ArrayRef<SMLoc> Loc) =0; 701de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 712c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger void apply(SetTheory &ST, DagInit *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc) { 721de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (Expr->arg_size() != 2) 7361131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Operator requires (Op Set, Int) arguments: " + 742c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger Expr->getAsString()); 751de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen RecSet Set; 762c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger ST.evaluate(Expr->arg_begin()[0], Set, Loc); 776cfc806a6b82b60a3e923b6b89f2b4da62cdb50bSean Silva IntInit *II = dyn_cast<IntInit>(Expr->arg_begin()[1]); 781de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (!II) 7961131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Second argument must be an integer: " + 802c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger Expr->getAsString()); 812c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger apply2(ST, Expr, Set, II->getValue(), Elts, Loc); 821de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 831de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen}; 841de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 851de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// (shl S, N) Shift left, remove the first N elements. 861de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenstruct ShlOp : public SetIntBinOp { 8705bce0beee87512e52428d4b80f5a8e79a949576David Greene void apply2(SetTheory &ST, DagInit *Expr, 881de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen RecSet &Set, int64_t N, 892c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger RecSet &Elts, ArrayRef<SMLoc> Loc) { 901de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (N < 0) 9161131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Positive shift required: " + 922c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger Expr->getAsString()); 931de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (unsigned(N) < Set.size()) 941de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Elts.insert(Set.begin() + N, Set.end()); 951de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 961de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen}; 971de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 981de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// (trunc S, N) Truncate after the first N elements. 991de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenstruct TruncOp : public SetIntBinOp { 10005bce0beee87512e52428d4b80f5a8e79a949576David Greene void apply2(SetTheory &ST, DagInit *Expr, 1011de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen RecSet &Set, int64_t N, 1022c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger RecSet &Elts, ArrayRef<SMLoc> Loc) { 1031de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (N < 0) 10461131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Positive length required: " + 1052c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger Expr->getAsString()); 1061de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (unsigned(N) > Set.size()) 1071de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen N = Set.size(); 1081de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Elts.insert(Set.begin(), Set.begin() + N); 1091de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 1101de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen}; 1111de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1121de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// Left/right rotation. 1131de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenstruct RotOp : public SetIntBinOp { 1141de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen const bool Reverse; 1151de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1161de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen RotOp(bool Rev) : Reverse(Rev) {} 1171de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 11805bce0beee87512e52428d4b80f5a8e79a949576David Greene void apply2(SetTheory &ST, DagInit *Expr, 1191de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen RecSet &Set, int64_t N, 1202c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger RecSet &Elts, ArrayRef<SMLoc> Loc) { 1211de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (Reverse) 1221de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen N = -N; 1231de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // N > 0 -> rotate left, N < 0 -> rotate right. 1241de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (Set.empty()) 1251de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen return; 1261de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (N < 0) 1271de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen N = Set.size() - (-N % Set.size()); 1281de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen else 1291de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen N %= Set.size(); 1301de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Elts.insert(Set.begin() + N, Set.end()); 1311de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Elts.insert(Set.begin(), Set.begin() + N); 1321de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 1331de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen}; 1341de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1351de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// (decimate S, N) Pick every N'th element of S. 1361de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenstruct DecimateOp : public SetIntBinOp { 13705bce0beee87512e52428d4b80f5a8e79a949576David Greene void apply2(SetTheory &ST, DagInit *Expr, 1381de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen RecSet &Set, int64_t N, 1392c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger RecSet &Elts, ArrayRef<SMLoc> Loc) { 1401de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (N <= 0) 14161131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Positive stride required: " + 1422c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger Expr->getAsString()); 1431de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen for (unsigned I = 0; I < Set.size(); I += N) 1441de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Elts.insert(Set[I]); 1451de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 1461de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen}; 1471de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1485b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen// (interleave S1, S2, ...) Interleave elements of the arguments. 1495b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesenstruct InterleaveOp : public SetTheory::Operator { 1502c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger void apply(SetTheory &ST, DagInit *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc) { 1515b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen // Evaluate the arguments individually. 1525b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen SmallVector<RecSet, 4> Args(Expr->getNumArgs()); 1535b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen unsigned MaxSize = 0; 1545b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen for (unsigned i = 0, e = Expr->getNumArgs(); i != e; ++i) { 1552c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger ST.evaluate(Expr->getArg(i), Args[i], Loc); 1565b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen MaxSize = std::max(MaxSize, unsigned(Args[i].size())); 1575b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen } 1585b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen // Interleave arguments into Elts. 1595b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen for (unsigned n = 0; n != MaxSize; ++n) 1605b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen for (unsigned i = 0, e = Expr->getNumArgs(); i != e; ++i) 1615b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen if (n < Args[i].size()) 1625b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen Elts.insert(Args[i][n]); 1635b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen } 1645b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen}; 1655b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen 1661de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// (sequence "Format", From, To) Generate a sequence of records by name. 1671de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenstruct SequenceOp : public SetTheory::Operator { 1682c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger void apply(SetTheory &ST, DagInit *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc) { 1696b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson int Step = 1; 1706b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson if (Expr->arg_size() > 4) 17161131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Bad args to (sequence \"Format\", From, To): " + 1722c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger Expr->getAsString()); 1736b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson else if (Expr->arg_size() == 4) { 1746cfc806a6b82b60a3e923b6b89f2b4da62cdb50bSean Silva if (IntInit *II = dyn_cast<IntInit>(Expr->arg_begin()[3])) { 1756b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson Step = II->getValue(); 1766b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson } else 17761131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Stride must be an integer: " + 17861131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger Expr->getAsString()); 1796b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson } 1806b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson 1811de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen std::string Format; 1826cfc806a6b82b60a3e923b6b89f2b4da62cdb50bSean Silva if (StringInit *SI = dyn_cast<StringInit>(Expr->arg_begin()[0])) 1831de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Format = SI->getValue(); 1841de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen else 18561131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Format must be a string: " + Expr->getAsString()); 1861de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1871de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen int64_t From, To; 1886cfc806a6b82b60a3e923b6b89f2b4da62cdb50bSean Silva if (IntInit *II = dyn_cast<IntInit>(Expr->arg_begin()[1])) 1891de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen From = II->getValue(); 1901de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen else 19161131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "From must be an integer: " + Expr->getAsString()); 1922559011a0176f7829effdad0a26395f14d723930Jakob Stoklund Olesen if (From < 0 || From >= (1 << 30)) 19361131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "From out of range"); 1940cc0929efcb5a137c351cd7e2fa70b0e2e97f313Jakob Stoklund Olesen 1956cfc806a6b82b60a3e923b6b89f2b4da62cdb50bSean Silva if (IntInit *II = dyn_cast<IntInit>(Expr->arg_begin()[2])) 1961de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen To = II->getValue(); 1971de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen else 19861131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "From must be an integer: " + Expr->getAsString()); 1992559011a0176f7829effdad0a26395f14d723930Jakob Stoklund Olesen if (To < 0 || To >= (1 << 30)) 20061131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "To out of range"); 2011de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 202c017bc1c1e2fa0995e957f6c2ada1339832bb221Jakob Stoklund Olesen RecordKeeper &Records = 2033f7b7f8ce0b050fc6a0100839d9c5a84198b2aedSean Silva cast<DefInit>(Expr->getOperator())->getDef()->getRecords(); 204c017bc1c1e2fa0995e957f6c2ada1339832bb221Jakob Stoklund Olesen 2056b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson Step *= From <= To ? 1 : -1; 2066b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson while (true) { 2076b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson if (Step > 0 && From > To) 2086b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson break; 2096b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson else if (Step < 0 && From < To) 2106b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson break; 2111de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen std::string Name; 2121de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen raw_string_ostream OS(Name); 2130cc0929efcb5a137c351cd7e2fa70b0e2e97f313Jakob Stoklund Olesen OS << format(Format.c_str(), unsigned(From)); 2141de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Record *Rec = Records.getDef(OS.str()); 2151de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (!Rec) 21661131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "No def named '" + Name + "': " + 2172c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger Expr->getAsString()); 2181de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // Try to reevaluate Rec in case it is a set. 2191de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (const RecVec *Result = ST.expand(Rec)) 2201de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Elts.insert(Result->begin(), Result->end()); 2211de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen else 2221de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Elts.insert(Rec); 2236b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson 2246b31d4ea3610b04d71e1eb38d8fc625eae7b759aOwen Anderson From += Step; 2251de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 2261de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 2271de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen}; 2281de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 2291de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// Expand a Def into a set by evaluating one of its fields. 2301de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenstruct FieldExpander : public SetTheory::Expander { 2311de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen StringRef FieldName; 2321de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 2331de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen FieldExpander(StringRef fn) : FieldName(fn) {} 2341de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 2351de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen void expand(SetTheory &ST, Record *Def, RecSet &Elts) { 2362c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger ST.evaluate(Def->getValueInit(FieldName), Elts, Def->getLoc()); 2371de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 2381de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen}; 2391de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen} // end anonymous namespace 2401de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 2412d24e2a396a1d211baaeedf32148a3b657240170David Blaikievoid SetTheory::Operator::anchor() { } 2422d24e2a396a1d211baaeedf32148a3b657240170David Blaikie 2432d24e2a396a1d211baaeedf32148a3b657240170David Blaikievoid SetTheory::Expander::anchor() { } 2442d24e2a396a1d211baaeedf32148a3b657240170David Blaikie 245c017bc1c1e2fa0995e957f6c2ada1339832bb221Jakob Stoklund OlesenSetTheory::SetTheory() { 2461de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen addOperator("add", new AddOp); 2471de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen addOperator("sub", new SubOp); 2481de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen addOperator("and", new AndOp); 2491de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen addOperator("shl", new ShlOp); 2501de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen addOperator("trunc", new TruncOp); 2511de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen addOperator("rotl", new RotOp(false)); 2521de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen addOperator("rotr", new RotOp(true)); 2531de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen addOperator("decimate", new DecimateOp); 2545b52f6d655e34de5c6fedbb71b6c94775cc10032Jakob Stoklund Olesen addOperator("interleave", new InterleaveOp); 255c017bc1c1e2fa0995e957f6c2ada1339832bb221Jakob Stoklund Olesen addOperator("sequence", new SequenceOp); 2561de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen} 2571de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 2581de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenvoid SetTheory::addOperator(StringRef Name, Operator *Op) { 2591de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Operators[Name] = Op; 2601de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen} 2611de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 2621de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenvoid SetTheory::addExpander(StringRef ClassName, Expander *E) { 2631de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Expanders[ClassName] = E; 2641de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen} 2651de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 2661de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenvoid SetTheory::addFieldExpander(StringRef ClassName, StringRef FieldName) { 2671de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen addExpander(ClassName, new FieldExpander(FieldName)); 2681de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen} 2691de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 2702c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenbergervoid SetTheory::evaluate(Init *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc) { 2711de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // A def in a list can be a just an element, or it may expand. 2726cfc806a6b82b60a3e923b6b89f2b4da62cdb50bSean Silva if (DefInit *Def = dyn_cast<DefInit>(Expr)) { 2731de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (const RecVec *Result = expand(Def->getDef())) 2741de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen return Elts.insert(Result->begin(), Result->end()); 2751de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Elts.insert(Def->getDef()); 2761de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen return; 2771de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 2781de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 2791de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // Lists simply expand. 2806cfc806a6b82b60a3e923b6b89f2b4da62cdb50bSean Silva if (ListInit *LI = dyn_cast<ListInit>(Expr)) 2812c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger return evaluate(LI->begin(), LI->end(), Elts, Loc); 2821de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 2831de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // Anything else must be a DAG. 2846cfc806a6b82b60a3e923b6b89f2b4da62cdb50bSean Silva DagInit *DagExpr = dyn_cast<DagInit>(Expr); 2851de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (!DagExpr) 28661131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Invalid set element: " + Expr->getAsString()); 2876cfc806a6b82b60a3e923b6b89f2b4da62cdb50bSean Silva DefInit *OpInit = dyn_cast<DefInit>(DagExpr->getOperator()); 2881de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (!OpInit) 28961131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Bad set expression: " + Expr->getAsString()); 2901de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen Operator *Op = Operators.lookup(OpInit->getDef()->getName()); 2911de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (!Op) 29261131ab15fd593a2e295d79fe2714e7bc21f2ec8Joerg Sonnenberger PrintFatalError(Loc, "Unknown set operator: " + Expr->getAsString()); 2932c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger Op->apply(*this, DagExpr, Elts, Loc); 2941de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen} 2951de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 2961de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenconst RecVec *SetTheory::expand(Record *Set) { 2971de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // Check existing entries for Set and return early. 2981de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen ExpandMap::iterator I = Expansions.find(Set); 2991de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen if (I != Expansions.end()) 3001de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen return &I->second; 3011de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 3021de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // This is the first time we see Set. Find a suitable expander. 3032c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger const std::vector<Record*> &SC = Set->getSuperClasses(); 3042c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger for (unsigned i = 0, e = SC.size(); i != e; ++i) { 3052c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger // Skip unnamed superclasses. 3062c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger if (!dyn_cast<StringInit>(SC[i]->getNameInit())) 3072c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger continue; 3082c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger if (Expander *Exp = Expanders.lookup(SC[i]->getName())) { 3092c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger // This breaks recursive definitions. 3102c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger RecVec &EltVec = Expansions[Set]; 3112c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger RecSet Elts; 3122c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger Exp->expand(*this, Set, Elts); 3132c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger EltVec.assign(Elts.begin(), Elts.end()); 3142c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger return &EltVec; 31513745262a8db98d6c4513ff9934db4be75a8b26cAndrew Trick } 3161de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 3171de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 3181de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // Set is not expandable. 3191de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen return 0; 3201de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen} 3211de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 322