SymbolicExpr.h

Go to the documentation of this file.

/*
 *      $Id$
 *      Symbolic Expression definition and processor
 *
 *      This file is part of OTAWA
 *      Copyright (c) 2011, 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
 */

#ifndef OTAWA_DATA_CLP_SYMBOLICEXPR_H_
#define OTAWA_DATA_CLP_SYMBOLICEXPR_H_

#include <elm/io.h>
#include <elm/io/Output.h>
#include <elm/genstruct/Vector.h>
#include <elm/string/AutoString.h>
#include <otawa/cfg/BasicBlock.h>
#include <otawa/data/clp/ClpValue.h>
#include <otawa/data/clp/ClpPack.h>

using namespace elm;
using namespace elm::genstruct;

namespace otawa {

namespace hard {
        class Platform;
}       // hard

namespace se{

        typedef clp::Value V;

        typedef enum {
                NONE,
                CONST,          
                ADDR,           
                REG,            
                NEG,            
                ADD,            
                CMP,            
                CMPU,           
                LE,                     
                LT,                     
                GE,                     
                GT,                     
                EQ,                     
                NE,                     
                ULE,
                ULT,
                UGE,
                UGT,
                OR
        } op_t;

        class SymbExpr{
        public:
                SymbExpr(op_t op=NONE, SymbExpr *a=NULL, SymbExpr *b=NULL, V val=0, SymbExpr *parent=NULL):
                        _op(op), _a(a), _b(b), _val(val), _parent(parent) {
                        ASSERT(_op >= NONE && _op <= OR);
                        if(_a != NULL)
                                _a->set_parent(this);
                        if(_b != NULL)
                                _b->set_parent(this);
                }
                SymbExpr(const SymbExpr &expr):
                        _op(expr._op), _val(expr._val), _parent(expr._parent) {
                        ASSERT(_op >= NONE && _op <= OR);
                        set_a(expr._a); // to copy expr._a
                        set_b(expr._b); // to copy expr._b
                }
                virtual ~SymbExpr(){
                        delete _a;
                        delete _b;
                        if (_parent != NULL){
                                if (_parent->_a == this)
                                        _parent->_a = NULL;
                                else if (_parent->_b == this)
                                        _parent->_b = NULL;
                        }
                }

                virtual SymbExpr* copy(void);
                virtual SymbExpr& operator=(const SymbExpr& expr);
                virtual bool operator==(const SymbExpr& expr) const;
                bool operator!=(const SymbExpr& expr) const;

                op_t op(void) const { return _op; }
                SymbExpr* a(void) const { return _a; }
                SymbExpr* b(void) const { return _b; }
                V val(void) const { return _val; }
                SymbExpr* parent(void) const { return _parent; }

                void replace(SymbExpr *searched_se, SymbExpr *new_se);
                virtual String asString(const hard::Platform *pf = 0);
                void print(io::Output& out, const hard::Platform *pf = 0);
                virtual void canonize(void);
                virtual Vector<V> used_reg(void);
                virtual Vector<V> used_addr(void);

                void set_a(SymbExpr *a){
                        SymbExpr *olda = _a;
                        if (a) {
                                _a = a->copy();
                                _a->set_parent(this);
                        } else
                                _a = NULL;
                        // in last, because a can be delete here, we must copy it before
                        delete olda;
                }
                void set_b(SymbExpr *b){
                        SymbExpr *oldb = _b;
                        if (b) {
                                _b = b->copy();
                                _b->set_parent(this);
                        } else
                                _b = NULL;
                        // in last, because b can be delete here, we must copy it before
                        delete oldb;
                }
                void set_parent(SymbExpr *parent) { _parent = parent ; }

        protected:
                op_t _op;
                SymbExpr *_a;
                SymbExpr *_b;
                V _val;
                SymbExpr *_parent;
        };

        class SEConst: public SymbExpr{
        public:
                SEConst(V value, SymbExpr *parent=NULL):
                        SymbExpr(CONST, NULL, NULL, value, parent) {}
                SEConst(const SEConst &expr): SymbExpr(expr) {}

                virtual SEConst* copy(void);
                virtual SymbExpr& operator=(const SEConst& expr);
                virtual bool operator==(const SymbExpr& expr) const;

                virtual String asString(const hard::Platform *pf = 0);
                virtual void canonize(void);
        };

        class SEAddr: public SymbExpr{
        public:
                SEAddr(V value, SymbExpr* parent=NULL):
                        SymbExpr(ADDR, NULL, NULL, value, parent) {}
                SEAddr(const SEAddr &expr): SymbExpr(expr) {}

                virtual SEAddr* copy(void);
                virtual SymbExpr& operator=(const SEAddr& expr);
                virtual bool operator==(const SymbExpr& expr) const;

                virtual String asString(const hard::Platform *pf = 0);
                virtual void canonize(void);
                virtual Vector<V> used_addr(void);
        };

        class SEReg: public SymbExpr{
        public:
                SEReg(V value, SymbExpr *parent=NULL):
                        SymbExpr(REG, NULL, NULL, value, parent) {}
                SEReg(const SEReg &expr): SymbExpr(expr) {}

                virtual SEReg* copy(void);
                virtual SymbExpr& operator=(const SEReg& expr);
                virtual bool operator==(const SymbExpr& expr) const;

                virtual String asString(const hard::Platform *pf = 0);
                virtual void canonize(void);
                virtual Vector<V> used_reg(void);
        };

        class SENeg: public SymbExpr{
        public:
                SENeg(SymbExpr *expr=NULL, SymbExpr *parent=NULL):
                        SymbExpr(NEG, expr, NULL, 0, parent) {}
                SENeg(const SENeg &expr): SymbExpr(expr) {}

                virtual SENeg* copy(void);
                virtual SymbExpr& operator=(const SENeg& expr);
                virtual bool operator==(const SymbExpr& expr) const;

                virtual String asString(const hard::Platform *pf = 0);
                virtual void canonize(void);
        };

        class SEAdd: public SymbExpr{
        public:
                SEAdd(SymbExpr *a=NULL, SymbExpr *b=NULL, SymbExpr *parent=NULL):
                        SymbExpr(ADD, a, b, 0, parent) {}
                SEAdd(const SEAdd &expr): SymbExpr(expr) {}

                virtual SEAdd* copy(void);
                virtual SymbExpr& operator=(const SEAdd& expr);
                virtual bool operator==(const SymbExpr& expr) const;

                virtual String asString(const hard::Platform *pf = 0);
                virtual void canonize(void);
        };

        class SECmp: public SymbExpr{
        public:
                SECmp(op_t op, SymbExpr *a=NULL, SymbExpr *b=NULL, SymbExpr *parent=NULL):
                        SymbExpr(op, a, b, 0, parent) {}
                SECmp(const SECmp &expr): SymbExpr(expr) {}

                virtual SECmp* copy(void);
                virtual SymbExpr& operator=(const SECmp& expr);
                virtual bool operator==(const SymbExpr& expr) const;

                virtual String asString(const hard::Platform *pf = 0);
                virtual void canonize(void);
                SECmp* logicalNot(void);
        };


        extern Identifier<Vector<SECmp *> > REG_FILTERS;
        extern Identifier<Vector<SECmp *> > ADDR_FILTERS;

        class FilterBuilder {
        public:
                FilterBuilder(BasicBlock *_bb, clp::ClpProblem& problem);
        private:
                void getFilters(void);
                void iterateBranchPaths(Inst *inst, const Vector<Inst *>& insts);
                sem::cond_t reverseCond(sem::cond_t cond);
                SECmp *makeFilters(SECmp *se, Inst *cur_inst, sem::Block& block);
                void addFilters(SECmp *se, const Vector<Inst *>& insts);

                BasicBlock *bb;
                Vector<SECmp *> reg_filters;
                Vector<SECmp *> addr_filters;
                Vector<V> known_reg;
                Vector<V> known_addr;
                clp::ClpStatePack pack;
        };


        void applyFilter(V &v, se::op_t cmp_op, V f);
} // se

} // otawa

inline io::Output& operator<<(io::Output& out, otawa::se::SymbExpr *sym)
        { out << "=> "; sym->print(out); return out; }
// output
inline elm::io::Output& operator<<(elm::io::Output& out, otawa::se::SymbExpr &se) {
        cerr << "ici !\n";
        se.print(out);
        return out;
}


#endif /* OTAWA_DATA_CLP_SYMBOLICEXPR_H_ */