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