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 4737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#ifndef LLVM_TABLEGEN_SETTHEORY_H 4837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines#define LLVM_TABLEGEN_SETTHEORY_H 491de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 506948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar#include "llvm/ADT/ArrayRef.h" 511de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#include "llvm/ADT/SetVector.h" 524ffd89fa4d2788611187d1a534d2ed46adf1702cChandler Carruth#include "llvm/ADT/StringMap.h" 536948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar#include "llvm/Support/SMLoc.h" 541de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#include <map> 551de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#include <vector> 561de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 571de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesennamespace llvm { 581de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 591de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenclass DagInit; 60afd54269ab9951c0dcdea076c4d6f48a345e9d27David Greeneclass Init; 611de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenclass Record; 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. 986948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar StringMap<std::unique_ptr<Operator>> Operators; 991de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1001de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // Typed expanders by class name. 1016948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar StringMap<std::unique_ptr<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. 1086948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar void addExpander(StringRef ClassName, std::unique_ptr<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. 1216948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar void addOperator(StringRef Name, std::unique_ptr<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