concepts.h

Go to the documentation of this file.

/*
 *      $Id$
 *      concept collection
 *
 *      This file is part of OTAWA
 *      Copyright (c) 2007, IRIT UPS.
 * 
 *      OTAWA is free software; you can redistribute it and/or modify
 *      it under the terms of the GNU General Public License as published by
 *      the Free Software Foundation; either version 2 of the License, or
 *      (at your option) any later version.
 *
 *      OTAWA is distributed in the hope that it will be useful,
 *      but WITHOUT ANY WARRANTY; without even the implied warranty of
 *      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *      GNU General Public License for more details.
 *
 *      You should have received a copy of the GNU General Public License
 *      along with OTAWA; if not, write to the Free Software 
 *      Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

#include <elm/genstruct/Vector.h>

using namespace elm;

namespace otawa { namespace concept {

class DiGraph: public elm::concept::Collection<Vertex> {
public:

        class Vertex { };
        
        class Edge { };

        const Vertex& sinkOf(Edge& edge);
        
        int outDegree(const Vertex& vertex) const;

        bool isSuccessorOf(Vertex& succ, const Vertex& ref);

        class Successor: public Iterator<Edge> {
        public:
                
                Successor(const DiGraph& graph, const Vertex& source);
                
                Successor(const OutIterator& iterator);
        };
        
};


class DiGraphWithLoop: public DiGraph {

        bool isLoopHeader(Vertex& vertex);
};


class DiGraphWithIndexedVertex: public DiGraph {
public:
        int indexOf(const Vertex& vertex) const;
};


class BiDiGraph: public DiGraph {

        class Predecessor: public Iterator<Edge> {
        public:
                
                Predecessor(const DiGraph& graph, const Vertex& source);
                
                Predecessor(const InIterator& iterator);
        };
        
        const Vertex& sourceOf(const Edge& edge);

        int inDegree(const Vertex& vertex) const;
        
        bool isSuccessorOf(const Vertex& succ, const Vertex& ref);
};


class DiGraphWithVertexMap: public DiGraph {
public: 
        template <class T> class VertexMap: public Map<Vertex, T> { };
};


class DiGraphWithEdgeMap: public DiGraph {
public:
        template <class T> class EdgeMap: public Map<Edge, T> { };
};


class DiGraphWithEntry: public DiGraph {
public:
        Vertex entry(void);
};


class DiGraphWithExit: public BiDiGraph {
public:
        Vertex exit(void);
};

class InstBlock {
public:

        Address address(void);

        size_t size(void);
        
        Address topAddress(void);

        int countInsts(void);
        
        class InstIter: public Iterator<Inst *> {
        public:
        
                InstIter(const InstBlock *block);
                
                InstIter(const InstIter& iter);
        };
};


template <class T, class G>
class AbstractDomain {
public:

        typedef T t;
        
        t initial(void);
        
        t bottom(void);
        
        void join(t& d, t s);
        
        bool equals(t v1, t v2);
        
        void set(t& d, t s);

        void dump(io::Output& out, t c);
        
        void update(const typename G::Vertex& vertex, t& d);

};

class IterativeDFAProblem {
public:

        typedef struct Set Set;
        
        Set *empty(void);

        Set *gen(BasicBlock *bb);
        
        Set *kill(BasicBlock *bb);

        bool equals(Set *set1, Set *set2);

        void reset(Set *set);
        
        void merge(Set *set1, Set *set2);
        
        void set(Set *dset, Set *tset);
        
        void add(Set *dset, Set *tset);
        
        void diff(Set *dset, Set *tset);
        
        void free(Set *set);
};

}       // dfa


namespace ai {

class Graph {
public:

        typedef void *vertex_t;

        typedef void *edge_t;

        vertex_t entry(void) const;

        vertex_t exit(void) const;

        vertex_t sinkOf(edge_t e) const;

        vertex_t sourceOf(edge_t e) const;

        class Predecessor {
        public:
                Predecessor(const CFGGraph& graph, vertex_t v);
                Predecessor(const Predecessor& p);
        };

        class Successor {
        public:
                Successor(const CFGGraph& graph, vertex_t v);
                Successor(const Successor& p);
        };

        class Iterator {
        public:
                Iterator(const CFGGraph& g);
                Iterator(const Iterator& i);
        };

        int index(vertex_t v) const;

        int count(void) const;
};


class Domain {
public:

        typedef void *t;

        t init(void);

        t bot(void);

        t join(t v1, t v2);

        bool equals(t v1, t v2);

        template <class I>
        t input(Graph::vertex_t vertex, I& ins);

        template <class O>
        void output(Graph::vertex_t vertex, t in, O& outs);

};

class InputIter {
public:

        Graph::edge_t edge(void);

        const Domain::t& get(void);
};

class OutputIter {
public:

        Graph::edge_t edge(void);

        void set(const Domain::t& value);

        void setAll(const Domain::t& value);
};

}       // ai

}       // otawa