Update copyright to LGPL on all files
[dyninst.git] / instructionAPI / h / Expression.h
1 /*
2  * Copyright (c) 1996-2009 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as "Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * By your use of Paradyn, you understand and agree that we (or any
12  * other person or entity with proprietary rights in Paradyn) are
13  * under no obligation to provide either maintenance services,
14  * update services, notices of latent defects, or correction of
15  * defects for Paradyn.
16  * 
17  * This library is free software; you can redistribute it and/or
18  * modify it under the terms of the GNU Lesser General Public
19  * License as published by the Free Software Foundation; either
20  * version 2.1 of the License, or (at your option) any later version.
21  * 
22  * This library is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25  * Lesser General Public License for more details.
26  * 
27  * You should have received a copy of the GNU Lesser General Public
28  * License along with this library; if not, write to the Free Software
29  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
30  */
31
32 #if !defined(VALUECOMPUTATION_H)
33 #define VALUECOMPUTATION_H
34
35
36 #include "InstructionAST.h"
37 #include "Result.h"
38
39 #include <dyn_detail/boost/shared_ptr.hpp>
40 #include <vector>
41 #include <sstream>
42
43 namespace Dyninst
44 {
45   namespace InstructionAPI
46   {
47  
48     class Expression;
49     class Visitor;
50     /// An %Expression is an AST representation of how the value of an
51     /// operand is computed.
52     ///
53     /// The %Expression class extends the %InstructionAST class by
54     /// adding the concept of evaluation to the nodes of an
55     /// %InstructionAST.  Evaluation attempts to determine the Result
56     /// of the computation that the AST being evaluated represents.
57     /// It will fill in results of as many of the nodes in the tree as
58     /// possible, and if full evaluation is possible, it will return
59     /// the result of the computation performed by the tree.
60     ///
61     /// Permissible leaf nodes of a %Expression tree are %RegisterAST
62     /// and %Immediate objects.  Permissible internal nodes are
63     /// %BinaryFunction and %Dereference objects.  An %Expression may
64     /// represent an immediate value, the contents of a register, or
65     /// the contents of memory at a given address, interpreted as a
66     /// particular type.
67     /// 
68     /// The %Results in an %Expression tree contain a type and a
69     /// value.  Their values may be an undefined value or an instance
70     /// of their associated type.  When two %Results are combined
71     /// using a %BinaryFunction, the %BinaryFunction specifies the
72     /// output type.  Sign extension, type promotion, truncation, and
73     /// all other necessary conversions are handled automatically
74     /// based on the input types and the output type.  If both of the
75     /// %Results that are combined have defined values, the
76     /// combination will also have a defined value; otherwise, the
77     /// combination's value will be undefined.  For more information,
78     /// see Result, BinaryFunction, and Dereference.
79     ///
80     /// A user may specify the result of evaluating a given
81     /// %Expression.  This mechanism is designed to allow the user to
82     /// provide a %Dereference or %RegisterAST with information about
83     /// the state of memory or registers.  It may additionally be used
84     /// to change the value of an %Immediate or to specify the result
85     /// of a %BinaryFunction.  This mechanism may be used to support
86     /// other advanced analyses.
87     ///
88     /// In order to make it more convenient to specify the results
89     /// of particular subexpressions, the \c bind method is provided.
90     /// \c bind allows the user to specify that a given subexpression
91     /// has a particular value everywhere that it appears in an expression.
92     /// For example, if the state of certain registers is known at the
93     /// time an instruction is executed, a user can \c bind those registers
94     /// to their known values throughout an %Expression.
95     ///
96     /// The evaluation mechanism, as mentioned above, will evaluate as
97     /// many sub-expressions of an expression as possible.  Any
98     /// operand that is more complicated than a single immediate
99     /// value, however, will depend on register or memory values.  The
100     /// %Results of evaluating each subexpression are cached
101     /// automatically using the \c setValue mechanism.  The
102     /// %Expression then attempts to determine its %Result based on
103     /// the %Results of its children.  If this %Result can be
104     /// determined (most likely because register contents have been
105     /// filled in via \c setValue or \c bind), it will be returned from \c eval;
106     /// if it can not be determined, a %Result with an undefined value
107     /// will be returned.  See Figure 6 for an illustration of this
108     /// concept; the operand represented is [ \c EBX + \c 4 * \c EAX
109     /// ].  The contents of \c EBX and \c EAX have been determined
110     /// through some outside mechanism, and have been defined with \c
111     /// setValue.  The \c eval mechanism proceeds to determine the
112     /// address being read by the %Dereference, since this information
113     /// can be determined given the contents of the registers.  This
114     /// address is available from the %Dereference through its child
115     /// in the tree, even though calling \c eval on the %Dereference
116     /// returns a %Result with an undefined value.  \dotfile
117     /// deref-eval.dot "Applying \c eval to a Dereference tree with
118     /// the state of the registers known and the state of memory
119     /// unknown"
120     ///
121     class INSTRUCTION_EXPORT Expression : public InstructionAST
122     {
123     public:
124       /// \brief A type definition for a reference counted pointer to a %Expression.
125       typedef dyn_detail::boost::shared_ptr<Expression> Ptr;
126       friend class Operation;
127     protected:      
128       Expression(Result_Type t);
129     public:
130       virtual ~Expression();
131
132       /// \brief If the %Expression can be evaluated, returns a %Result containing its value.
133       /// Otherwise returns an undefined %Result.
134       virtual const Result& eval() const;
135   
136       /// \param knownValue Sets the result of \c eval for this %Expression
137       /// to \c knownValue
138       void setValue(const Result& knownValue);
139   
140       /// \c clearValue sets the contents of this %Expression to undefined.
141       /// The next time \c eval is called, it will recalculate the value of the %Expression.
142       void clearValue();
143
144       /// \c size returns the size of this %Expression's %Result, in bytes.
145       int size() const;
146           
147       /// \c bind searches for all instances of the %Expression \c expr within
148       /// this %Expression, and sets the result of \c eval for those subexpressions
149       /// to \c value.  \c bind returns true if at least one instance of \c expr
150       /// was found in this %Expression.
151       ///
152       /// \c bind does not operate on subexpressions that happen to evaluate to
153       /// the same value.  For example, if a dereference of 0xDEADBEEF is bound to
154       /// 0, and a register is bound to 0xDEADBEEF, a dereference of that register is not
155       /// bound to 0.
156       virtual bool bind(Expression* expr, const Result& value);
157       
158       virtual void apply(Visitor*) {}
159
160     protected:
161       virtual bool isFlag() const;
162     private:
163       Result userSetValue;
164       
165     };
166     class INSTRUCTION_EXPORT DummyExpr : public Expression
167     {
168         public:
169             virtual void getChildren(vector<InstructionAST::Ptr>& ) const {};
170             virtual void getUses(set<InstructionAST::Ptr>& ) {};
171             virtual bool isUsed(InstructionAST::Ptr ) const { return true;};
172             virtual std::string format() const { return "[WILDCARD]";};
173             DummyExpr() : Expression(u8) {}
174         protected:
175             virtual bool isStrictEqual(const InstructionAST& rhs) const;
176             virtual bool checkRegID(unsigned int id) const;
177     };
178
179   };
180 };
181
182
183
184 #endif //!defined(VALUECOMPUTATION_H)
185