SetTheory.h revision 2c6d71388fb1b68ce6fdbb88642a95a24b27b2a7
11de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen//===- SetTheory.h - Generate ordered sets from DAG expressions -*- C++ -*-===// 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. Operators for standard set operations are 121de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// predefined, and it is possible to add special purpose set operators as well. 131de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 141de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// The user may define named sets as Records of predefined classes. Set 151de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// expanders can be added to a SetTheory instance to teach it how to find the 161de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// elements of such a named set. 171de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 181de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// These are the predefined operators. The argument lists can be individual 191de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// elements (defs), other sets (defs of expandable classes), lists, or DAG 201de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// expressions that are evaluated recursively. 211de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 221de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// - (add S1, S2 ...) Union sets. This is also how sets are created from element 231de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// lists. 241de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 251de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// - (sub S1, S2, ...) Set difference. Every element in S1 except for the 261de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// elements in S2, ... 271de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 281de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// - (and S1, S2) Set intersection. Every element in S1 that is also in S2. 291de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 301de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// - (shl S, N) Shift left. Remove the first N elements from S. 311de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 321de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// - (trunc S, N) Truncate. The first N elements of S. 331de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 341de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// - (rotl S, N) Rotate left. Same as (add (shl S, N), (trunc S, N)). 351de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 361de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// - (rotr S, N) Rotate right. 371de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 381de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// - (decimate S, N) Decimate S by picking every N'th element, starting with 391de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// the first one. For instance, (decimate S, 2) returns the even elements of 401de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// S. 411de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 421de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// - (sequence "Format", From, To) Generate a sequence of defs with printf. 431de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// For instance, (sequence "R%u", 0, 3) -> [ R0, R1, R2, R3 ] 441de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen// 451de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 461de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 471de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#ifndef SETTHEORY_H 481de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#define SETTHEORY_H 491de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 501de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#include "llvm/ADT/StringMap.h" 511de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#include "llvm/ADT/SetVector.h" 522c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger#include "llvm/Support/SourceMgr.h" 531de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#include <map> 541de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#include <vector> 551de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 561de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesennamespace llvm { 571de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 581de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenclass DagInit; 59afd54269ab9951c0dcdea076c4d6f48a345e9d27David Greeneclass Init; 601de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenclass Record; 611de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenclass RecordKeeper; 621de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 631de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenclass SetTheory { 641de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenpublic: 651de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen typedef std::vector<Record*> RecVec; 661de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen typedef SmallSetVector<Record*, 16> RecSet; 671de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 681de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// Operator - A callback representing a DAG operator. 692d24e2a396a1d211baaeedf32148a3b657240170David Blaikie class Operator { 702d24e2a396a1d211baaeedf32148a3b657240170David Blaikie virtual void anchor(); 712d24e2a396a1d211baaeedf32148a3b657240170David Blaikie public: 721023f5a42d82fca71c191dd6c1001f79e07c63aeJakob Stoklund Olesen virtual ~Operator() {} 731023f5a42d82fca71c191dd6c1001f79e07c63aeJakob Stoklund Olesen 741de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// apply - Apply this operator to Expr's arguments and insert the result 751de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// in Elts. 762c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger virtual void apply(SetTheory&, DagInit *Expr, RecSet &Elts, 772c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger ArrayRef<SMLoc> Loc) =0; 781de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen }; 791de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 801de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// Expander - A callback function that can transform a Record representing a 811de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// set into a fully expanded list of elements. Expanders provide a way for 821de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// users to define named sets that can be used in DAG expressions. 832d24e2a396a1d211baaeedf32148a3b657240170David Blaikie class Expander { 842d24e2a396a1d211baaeedf32148a3b657240170David Blaikie virtual void anchor(); 852d24e2a396a1d211baaeedf32148a3b657240170David Blaikie public: 861023f5a42d82fca71c191dd6c1001f79e07c63aeJakob Stoklund Olesen virtual ~Expander() {} 871023f5a42d82fca71c191dd6c1001f79e07c63aeJakob Stoklund Olesen 881de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen virtual void expand(SetTheory&, Record*, RecSet &Elts) =0; 891de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen }; 901de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 911de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenprivate: 921de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // Map set defs to their fully expanded contents. This serves as a memoization 931de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // cache and it makes it possible to return const references on queries. 941de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen typedef std::map<Record*, RecVec> ExpandMap; 951de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen ExpandMap Expansions; 961de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 971de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // Known DAG operators by name. 981de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen StringMap<Operator*> Operators; 991de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1001de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // Typed expanders by class name. 1011de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen StringMap<Expander*> Expanders; 1021de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1031de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenpublic: 1041de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// Create a SetTheory instance with only the standard operators. 105c017bc1c1e2fa0995e957f6c2ada1339832bb221Jakob Stoklund Olesen SetTheory(); 1061de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1071de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// addExpander - Add an expander for Records with the named super class. 1081de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen void addExpander(StringRef ClassName, Expander*); 1091de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1101de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// addFieldExpander - Add an expander for ClassName that simply evaluates 1111de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// FieldName in the Record to get the set elements. That is all that is 1121de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// needed for a class like: 1131de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// 1141de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// class Set<dag d> { 1151de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// dag Elts = d; 1161de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// } 1171de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// 1181de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen void addFieldExpander(StringRef ClassName, StringRef FieldName); 1191de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1201de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// addOperator - Add a DAG operator. 1211de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen void addOperator(StringRef Name, Operator*); 1221de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1231de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// evaluate - Evaluate Expr and append the resulting set to Elts. 1242c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger void evaluate(Init *Expr, RecSet &Elts, ArrayRef<SMLoc> Loc); 1251de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1261de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// evaluate - Evaluate a sequence of Inits and append to Elts. 1271de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen template<typename Iter> 1282c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger void evaluate(Iter begin, Iter end, RecSet &Elts, ArrayRef<SMLoc> Loc) { 1291de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen while (begin != end) 1302c6d71388fb1b68ce6fdbb88642a95a24b27b2a7Joerg Sonnenberger evaluate(*begin++, Elts, Loc); 1311de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 1321de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1331de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// expand - Expand a record into a set of elements if possible. Return a 1341de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// pointer to the expanded elements, or NULL if Set cannot be expanded 1351de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// further. 1361de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen const RecVec *expand(Record *Set); 1371de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen}; 1381de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1391de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen} // end namespace llvm 1401de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1411de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#endif 1421de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 143