managed.h

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2003, Mike Van Emmerik
00003  *
00004  * See the file "LICENSE.TERMS" for information on usage and
00005  * redistribution of this file, and for a DISCLAIMER OF ALL
00006  * WARRANTIES.
00007  *
00008  */
00009 
00010 /*===============================================================================================
00011  * FILE:       managed.h
00012  * OVERVIEW:   Definition of "managed" classes such as StatementSet, which feature makeUnion etc
00013  * CLASSES:     StatementSet
00014  *              AssignSet
00015  *              StatementList
00016  *              StatementVec
00017  *              LocationSet
00018  *              //LocationList
00019  *              ConnectionGraph
00020  *==============================================================================================*/
00021 
00022 /*
00023  * $Revision: 1.22 $    // 1.11.2.15
00024  *
00025  * 26/Aug/03 - Mike: Split off from statement.h
00026  */
00027 
00028 #ifndef __MANAGED_H__
00029 #define __MANAGED_H__
00030 
00031 #include <list>
00032 #include <set>
00033 #include <vector>
00034 
00035 #include "exphelp.h"        // For lessExpStar
00036 
00037 class Statement;
00038 class Assign;
00039 class Exp;
00040 class RefExp;
00041 class Cfg;
00042 class LocationSet;
00043 
00044 // A class to implement sets of statements
00045 class StatementSet {
00046         std::set<Statement*> sset;                          // For now, use use standard sets
00047 
00048 public:
00049 typedef std::set<Statement*>::iterator iterator;
00050 
00051                     ~StatementSet() {}
00052         void        makeUnion(StatementSet& other);     // Set union
00053         void        makeDiff (StatementSet& other);     // Set difference
00054         void        makeIsect(StatementSet& other);     // Set intersection
00055         bool        isSubSetOf(StatementSet& other);    // Subset relation
00056 
00057         unsigned    size() {return sset.size();}        // Number of elements
00058         iterator    begin() {return sset.begin();}
00059         iterator    end()   {return sset.end();}
00060         
00061         void        insert(Statement* s) {sset.insert(s);}  // Insertion
00062         bool        remove(Statement* s);                   // Removal; rets false if not found
00063         bool        removeIfDefines(Exp* given);            // Remove if given exp is defined
00064         bool        removeIfDefines(StatementSet& given);   // Remove if any given is def'd
00065         bool        exists(Statement* s);                   // Search; returns false if !found
00066         bool        definesLoc(Exp* loc);                   // Search; returns true if any
00067                                                             // statement defines loc
00068         void        clear() {sset.clear();}                 // Clear the set
00069         bool        operator==(const StatementSet& o) const // Compare if equal
00070                         { return sset == o.sset;}
00071         bool        operator<(const StatementSet& o) const; // Compare if less
00072         void        print(std::ostream& os);                // Print to os
00073         void        printNums(std::ostream& os);            // Print statements as numbers
00074         char*       prints();                               // Print to string (for debug)
00075         void        dump();                                 // Print to standard error for debugging
00076 };      // class StatementSet
00077 
00078 // As above, but the Statements are known to be Assigns, and are sorted sensibly
00079 class AssignSet {
00080         std::set<Assign*, lessAssign> aset;         // For now, use use standard sets
00081 
00082 public:
00083 typedef std::set<Assign*, lessAssign>::iterator iterator;
00084 typedef std::set<Assign*, lessAssign>::const_iterator const_iterator;
00085 
00086                     ~AssignSet() {}
00087         void        makeUnion(AssignSet& other);        // Set union
00088         void        makeDiff (AssignSet& other);        // Set difference
00089         void        makeIsect(AssignSet& other);        // Set intersection
00090         bool        isSubSetOf(AssignSet& other);       // Subset relation
00091 
00092         unsigned    size() {return aset.size();}        // Number of elements
00093         //Statement* getFirst(StmtSetIter& it);         // Get the first Statement
00094         //Statement* getNext (StmtSetIter& it);         // Get next
00095         iterator    begin() {return aset.begin();}
00096         iterator    end()   {return aset.end();}
00097         
00098         void        insert(Assign* a) {aset.insert(a);}     // Insertion
00099         bool        remove(Assign* a);                      // Removal; rets false if not found
00100         bool        removeIfDefines(Exp* given);            // Remove if given exp is defined
00101         bool        removeIfDefines(AssignSet& given);      // Remove if any given is def'd
00102         bool        exists(Assign* s);                      // Search; returns false if !found
00103         bool        definesLoc(Exp* loc);                   // Search; returns true if any assignment defines loc
00104         Assign*     lookupLoc(Exp* loc);                    // Search for loc on LHS, return ptr to Assign if found
00105 
00106         void        clear() {aset.clear();}                 // Clear the set
00107         bool        operator==(const AssignSet& o) const    // Compare if equal
00108                         { return aset == o.aset;}
00109         bool        operator<(const AssignSet& o) const;    // Compare if less
00110         void        print(std::ostream& os);                // Print to os
00111         void        printNums(std::ostream& os);            // Print statements as numbers
00112         char*       prints();                               // Print to string (for debug)
00113         void        dump();                                 // Print to standard error for debugging
00114         //bool  isLast(StmtSetIter& it);                    // returns true if it is at end
00115 };      // class AssignSet
00116 
00117 class StatementList {
00118         std::list<Statement*> slist;                        // For now, use use standard list
00119 
00120 public:
00121 typedef std::list<Statement*>::iterator iterator;
00122 typedef std::list<Statement*>::reverse_iterator reverse_iterator;
00123                     ~StatementList() {}
00124         unsigned    size() {return slist.size();}           // Number of elements
00125         iterator    begin()  {return slist.begin();}
00126         iterator    end()     {return slist.end();}
00127         reverse_iterator rbegin() {return slist.rbegin();}
00128         reverse_iterator rend()   {return slist.rend();}
00129 
00130         // A special intersection operator; this becomes the intersection of StatementList a (assumed to be a list of
00131         // Assignment*s) with the LocationSet b.
00132         // Used for calculating returns for a CallStatement
00133         void        makeIsect(StatementList& a, LocationSet& b);
00134         
00135         void        append(Statement* s) {slist.push_back(s);} // Insert at end
00136         void        append(StatementList& sl);          // Append whole StatementList
00137         void        append(StatementSet& sl);           // Append whole StatementSet
00138         bool        remove(Statement* s);               // Removal; rets false if not found
00139         void        removeDefOf(Exp* loc);              // Remove definitions of loc
00140         // This one is needed where you remove in the middle of a loop
00141         // Use like this: it = mystatementlist.erase(it);
00142         iterator    erase(iterator it) {return slist.erase(it);}
00143         iterator    erase(iterator first, iterator last) {return slist.erase(first, last);}
00144         iterator    insert(iterator it, Statement* s) {return slist.insert(it, s);}
00145         bool        exists(Statement* s);               // Search; returns false if not found
00146         char*       prints();                           // Print to string (for debugging)
00147         void        dump();                             // Print to standard error for debugging
00148         void        clear() { slist.clear(); }
00149         void        makeCloneOf(StatementList& o);      // Make this a clone of o
00150         bool        existsOnLeft(Exp* loc);             // True if loc exists on the LHS of any Assignment in this list
00151         Assignment* findOnLeft(Exp* loc);               // Return the first stmt with loc on the LHS
00152 };      // class StatementList
00153 
00154 class StatementVec {
00155         std::vector<Statement*> svec;           // For now, use use standard vector
00156 
00157 public:
00158 typedef std::vector<Statement*>::iterator iterator;
00159 typedef std::vector<Statement*>::reverse_iterator reverse_iterator;
00160         unsigned    size() {return svec.size();}            // Number of elements
00161         iterator    begin() { return svec.begin();}
00162         iterator    end()    { return svec.end();}
00163         reverse_iterator rbegin() { return svec.rbegin();}
00164         reverse_iterator rend()   { return svec.rend();}
00165         // Get/put at position idx (0 based)
00166         Statement* operator[](int idx) {return svec[idx];}
00167         void        putAt(int idx, Statement* s);
00168         iterator    remove(iterator it);
00169         char*       prints();                               // Print to string (for debugging)
00170         void        dump();                                 // Print to standard error for debugging
00171         void        printNums(std::ostream& os);
00172         void        clear() { svec.clear(); }
00173         bool        operator==(const StatementVec& o) const // Compare if equal
00174                         { return svec == o.svec;}
00175         bool        operator<(const StatementVec& o) const      // Compare if less
00176                         { return svec < o.svec;}
00177         void        append(Statement* s) {svec.push_back(s);}
00178         void        erase(iterator it) {svec.erase(it);}
00179 };  // class StatementVec
00180 
00181 // For various purposes, we need sets of locations (registers or memory)
00182 class LocationSet {
00183         // We use a standard set, but with a special "less than" operator so that the sets are ordered
00184         // by expression value. If this is not done, then two expressions with the same value (say r[10])
00185         // but that happen to have different addresses (because they came from different statements)
00186         // would both be stored in the set (instead of the required set behaviour, where only one is stored)
00187         std::set<Exp*, lessExpStar> lset; 
00188 public:
00189 typedef std::set<Exp*, lessExpStar>::iterator iterator;
00190                     LocationSet() {}                        // Default constructor
00191                     ~LocationSet() {}                       // virtual destructor kills warning
00192                     LocationSet(const LocationSet& o);      // Copy constructor
00193                     LocationSet& operator=(const LocationSet& o); // Assignment
00194         void        makeUnion(LocationSet& other);          // Set union
00195         void        makeDiff (LocationSet& other);          // Set difference
00196         void        clear() {lset.clear();}                 // Clear the set
00197         iterator    begin() {return lset.begin();}
00198         iterator    end()    {return lset.end();}
00199         void        insert(Exp* loc) {lset.insert(loc);}    // Insert the given location
00200         void        remove(Exp* loc);                       // Remove the given location
00201         void        remove(iterator ll) {lset.erase(ll);}   // Remove location, given iterator
00202         void        removeIfDefines(StatementSet& given);   // Remove locs defined in given
00203         unsigned    size() const {return lset.size();}      // Number of elements
00204         bool        operator==(const LocationSet& o) const; // Compare
00205         void        substitute(Assign& a);                  // Substitute the given assignment to all
00206         void        print(std::ostream& os);                // Print to os
00207         char*       prints();                               // Print to string for debugging
00208         void        dump();
00209         void        diff(LocationSet* o);                   // Diff 2 location sets to std::cerr
00210         bool        exists(Exp* e);                         // Return true if the location exists in the set
00211         Exp*        findNS(Exp* e);                         // Find location e (no subscripts); NULL if not found
00212         bool        existsImplicit(Exp* e);                 // Search for location e{-} or e{0} (e has no subscripts)
00213         // Return an iterator to the found item (or end() if not). Only really makes sense if e has a wildcard
00214         iterator    find(Exp* e) {return lset.find(e); }
00215         // Find a location with a different def, but same expression. For example, pass r28{10},
00216         // return true if r28{20} in the set. If return true, dr points to the first different ref
00217         bool        findDifferentRef(RefExp* e, Exp *&dr);
00218         void        addSubscript(Statement* def /* , Cfg* cfg */);      // Add a subscript to all elements
00219 };  // class LocationSet
00220 
00221 class Range {
00222 protected:
00223     int stride, lowerBound, upperBound;
00224     Exp *base;
00225 
00226 public:
00227     Range();
00228     Range(int stride, int lowerBound, int upperBound, Exp *base);
00229 
00230         Exp         *getBase() { return base; }
00231         int         getStride() { return stride; }
00232         int         getLowerBound() { return lowerBound; }
00233         int         getUpperBound() { return upperBound; }
00234         void        unionWith(Range &r);
00235         void        widenWith(Range &r);
00236         void        print(std::ostream &os);
00237         bool        operator==(Range &other);
00238     
00239 static const int MAX = 2147483647;
00240 static const int MIN = -2147483647;
00241 };
00242 
00243 class RangeMap {
00244 protected:
00245         std::map<Exp*, Range, lessExpStar> ranges;
00246 
00247 public:
00248                     RangeMap() { }
00249         void        addRange(Exp *loc, Range &r) { ranges[loc] = r; }
00250         bool        hasRange(Exp *loc) { return ranges.find(loc) != ranges.end(); }
00251         Range       &getRange(Exp *loc);
00252         void        unionwith(RangeMap &other);
00253         void        widenwith(RangeMap &other);
00254         void        print(std::ostream &os);
00255         Exp         * substInto(Exp *e, std::set<Exp*, lessExpStar> *only = NULL);
00256         void        killAllMemOfs();
00257         void        clear() { ranges.clear(); }
00258         bool        isSubset(RangeMap &other);
00259         bool        empty() { return ranges.empty(); }
00260 };
00261 
00262 /// A class to store connections in a graph, e.g. for interferences of types or live ranges, or the phi_unite relation
00263 /// that phi statements imply
00264 /// If a is connected to b, then b is automatically connected to a
00265 // This is implemented in a std::multimap, even though Appel suggests a bitmap (e.g. std::vector<bool> does this in a
00266 // space efficient manner), but then you still need maps from expression to bit number. So here a standard map is used,
00267 // and when a -> b is inserted, b->a is redundantly inserted.
00268 class ConnectionGraph {
00269     std::multimap<Exp*, Exp*, lessExpStar> emap;                // The map
00270 public:
00271 typedef std::multimap<Exp*, Exp*, lessExpStar>::iterator iterator;
00272                     ConnectionGraph() {}
00273 
00274         void        add(Exp* a, Exp* b);            // Add pair with check for existing
00275         void        connect(Exp* a, Exp* b);
00276         iterator    begin() {return emap.begin();}
00277         iterator    end() {return emap.end();}
00278         int         count(Exp* a);                  // Return a count of locations connected to a
00279         bool        isConnected(Exp* a, Exp* b);    // Return true if a is connected to b
00280         // Update the map that used to be a <-> b, now it is a <-> c
00281         void        update(Exp* a, Exp* b, Exp* c);
00282         iterator    remove(iterator aa);            // Remove the mapping at *aa
00283         void        dump();                         // Dump for debugging
00284 };
00285 
00286 #endif  // #ifdef __MANAGED_H__

Generated on Tue Sep 19 21:18:25 2006 for Boomerang by  doxygen 1.4.6