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