SetTheory.h revision afd54269ab9951c0dcdea076c4d6f48a345e9d27
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" 521de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#include <map> 531de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#include <vector> 541de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 551de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesennamespace llvm { 561de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 571de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenclass DagInit; 58afd54269ab9951c0dcdea076c4d6f48a345e9d27David Greeneclass Init; 591de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenclass Record; 601de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenclass RecordKeeper; 611de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 621de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenclass SetTheory { 631de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenpublic: 641de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen typedef std::vector<Record*> RecVec; 651de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen typedef SmallSetVector<Record*, 16> RecSet; 661de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 671de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// Operator - A callback representing a DAG operator. 681de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen struct Operator { 691023f5a42d82fca71c191dd6c1001f79e07c63aeJakob Stoklund Olesen virtual ~Operator() {} 701023f5a42d82fca71c191dd6c1001f79e07c63aeJakob Stoklund Olesen 711de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// apply - Apply this operator to Expr's arguments and insert the result 721de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// in Elts. 73d568b3f55294917d1cc701da14a8a7daeb6563e6Eric Christopher virtual void apply(SetTheory&, DagInit *Expr, RecSet &Elts) =0; 741de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen }; 751de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 761de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// Expander - A callback function that can transform a Record representing a 771de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// set into a fully expanded list of elements. Expanders provide a way for 781de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// users to define named sets that can be used in DAG expressions. 791de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen struct Expander { 801023f5a42d82fca71c191dd6c1001f79e07c63aeJakob Stoklund Olesen virtual ~Expander() {} 811023f5a42d82fca71c191dd6c1001f79e07c63aeJakob Stoklund Olesen 821de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen virtual void expand(SetTheory&, Record*, RecSet &Elts) =0; 831de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen }; 841de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 851de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenprivate: 861de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // Map set defs to their fully expanded contents. This serves as a memoization 871de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // cache and it makes it possible to return const references on queries. 881de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen typedef std::map<Record*, RecVec> ExpandMap; 891de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen ExpandMap Expansions; 901de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 911de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // Known DAG operators by name. 921de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen StringMap<Operator*> Operators; 931de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 941de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen // Typed expanders by class name. 951de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen StringMap<Expander*> Expanders; 961de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 971de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesenpublic: 981de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// Create a SetTheory instance with only the standard operators. 99c017bc1c1e2fa0995e957f6c2ada1339832bb221Jakob Stoklund Olesen SetTheory(); 1001de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1011de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// addExpander - Add an expander for Records with the named super class. 1021de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen void addExpander(StringRef ClassName, Expander*); 1031de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1041de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// addFieldExpander - Add an expander for ClassName that simply evaluates 1051de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// FieldName in the Record to get the set elements. That is all that is 1061de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// needed for a class like: 1071de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// 1081de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// class Set<dag d> { 1091de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// dag Elts = d; 1101de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// } 1111de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// 1121de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen void addFieldExpander(StringRef ClassName, StringRef FieldName); 1131de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1141de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// addOperator - Add a DAG operator. 1151de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen void addOperator(StringRef Name, Operator*); 1161de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1171de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// evaluate - Evaluate Expr and append the resulting set to Elts. 118d568b3f55294917d1cc701da14a8a7daeb6563e6Eric Christopher void evaluate(Init *Expr, RecSet &Elts); 1191de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1201de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// evaluate - Evaluate a sequence of Inits and append to Elts. 1211de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen template<typename Iter> 1221de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen void evaluate(Iter begin, Iter end, RecSet &Elts) { 1231de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen while (begin != end) 1241de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen evaluate(*begin++, Elts); 1251de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen } 1261de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1271de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// expand - Expand a record into a set of elements if possible. Return a 1281de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// pointer to the expanded elements, or NULL if Set cannot be expanded 1291de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen /// further. 1301de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen const RecVec *expand(Record *Set); 1311de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen}; 1321de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1331de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen} // end namespace llvm 1341de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 1351de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen#endif 1361de99829b6bebe3310682efac8be2a9a95323220Jakob Stoklund Olesen 137