Make SymEval an exported header
[dyninst.git] / symEval / src / SymEvalPolicy.h
1 /*
2  * Copyright (c) 1996-2007 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 // "Policy" class specification for interfacing with the ROSE
33 // instruction semantics engine. 
34 //
35 // Background:
36 //   The ROSE compiler suite provides a description of x86 instruction
37 // semantics. This operates in terms of a "policy" that states how each
38 // ROSE operation should map to your particular use. This policy class
39 // builds an AST representation of the instruction.
40 // 
41 // The instruction semantics is initialized with a copy of this class as
42 // a template parameter:
43 // AST_Policy policy;
44 // X86InstructionSemantics semantics<policy>;
45 // 
46 // The engine also takes a datatype template parameter which itself is
47 // parameterized on the bitsize of the data (e.g., 1, 16, 32, ...), so the
48 // more proper version is:
49 // X86InstructionSemantics semantics<policy, policy::Datatype>;
50 //
51 // where Datatype must take an int template parameter.
52
53 #if !defined(Sym_Eval_Policy_h)
54 #define Sym_Eval_Policy_h
55
56 #include "AST.h"
57 #include "Operation.h"
58 #include "Absloc.h"
59
60 #include <iostream>
61 #include <fstream>
62
63 #include "../rose/SgAsmx86Instruction.h"
64
65 // Also need ROSE header files... argh. 
66
67 // For typedefs
68 #include "SymEval.h"
69
70 namespace Dyninst {
71
72 namespace SymbolicEvaluation {
73
74 template <size_t Len>
75 struct Handle {
76   AST::Ptr *v_;
77   Handle() : v_(NULL) {
78     assert(0);
79   };
80   Handle(AST::Ptr v) {
81     assert(v);
82     v_ = new AST::Ptr(v);
83   };
84   Handle(const Handle &rhs) {
85     v_ = new AST::Ptr(rhs.var());
86   }
87   Handle operator=(const Handle &rhs) {
88     if (v_) delete v_;
89     v_ = new AST::Ptr(rhs.var());
90     return  *this;
91   }
92     ~Handle() { if (v_) delete v_; };
93   
94   template <size_t Len2>
95   bool operator==(const Handle<Len2> &rhs) {
96     return ((Len == Len2) && (*(var()) == *(rhs.var())));
97   }
98
99   AST::Ptr var() const { 
100     assert(v_); return *v_;
101   }
102   
103   //operator AST::Ptr() const { return *var; }
104   //AST::Ptr operator->() const { return *var; }
105 };
106
107
108  class SymEvalPolicy {
109  public:
110
111
112    SymEvalPolicy(SymEval::Result &r, 
113                  Address addr,
114                  Dyninst::Architecture a);
115
116    ~SymEvalPolicy() {};
117   
118    void startInstruction(SgAsmx86Instruction *);
119
120    void finishInstruction(SgAsmx86Instruction *);
121     
122    // Policy classes must implement the following methods:
123    Handle<32> readGPR(X86GeneralPurposeRegister r) {
124      return Handle<32>(wrap(convert(r)));
125    }
126     
127    void writeGPR(X86GeneralPurposeRegister r, Handle<32> value) {
128      std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(convert(r));
129      if (i != aaMap.end()) {
130        res[i->second] = value.var();
131      } 
132      // Otherwise we don't care. Annoying that we 
133      // had to expand this register...
134    }
135     
136    Handle<16> readSegreg(X86SegmentRegister r) {
137      return Handle<16>(wrap(convert(r)));
138    }
139     
140    void writeSegreg(X86SegmentRegister r, Handle<16> value) {
141      std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(convert(r));
142      if (i != aaMap.end()) {
143        res[i->second] = value.var();
144      }
145      // Otherwise we don't care. Annoying that we 
146      // had to expand this register...
147    }
148     
149    Handle<32> readIP() { 
150      return ip_;
151    }
152     
153    void writeIP(Handle<32> value) {
154      // Always care about the IP...
155      std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(Absloc::makePC(arch));
156      if (i != aaMap.end()) {
157        res[i->second] = value.var();
158      }
159      ip_ = value;
160      // Otherwise we don't care. Annoying that we 
161      // had to expand this register...
162    } 
163     
164    Handle<1> readFlag(X86Flag f) {
165      return Handle<1>(wrap(convert(f)));
166    }
167     
168    void writeFlag(X86Flag f, Handle<1> value) {
169      std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(convert(f));
170      if (i != aaMap.end()) {
171        res[i->second] = value.var();
172      }
173      // Otherwise we don't care. Annoying that we 
174      // had to expand this register...
175    }
176
177    // Len here is the number of bits read, which we'll
178    // turn into an argument of the AST. 
179     
180    template <size_t Len>
181      Handle<Len> readMemory(X86SegmentRegister /*segreg*/,
182                             Handle<32> addr,
183                             Handle<1> cond) {
184      if (cond == true_()) {
185        return Handle<Len>(getUnaryAST(ROSEOperation::derefOp,
186                                       addr.var()));
187      }
188      else {
189        return Handle<Len>(getBinaryAST(ROSEOperation::derefOp,
190                                        addr.var(),
191                                        cond.var()));
192      }
193    }
194         
195    template <size_t Len>
196      void writeMemory(X86SegmentRegister,
197                       Handle<32> addr,
198                       Handle<Len> data,
199                       Handle<32> repeat,
200                       Handle<1> cond) {
201      // We can only write memory once per instruction. Therefore, 
202      // instead of sweating what we're actually being handed (or
203      // what AbsRegion we're actually assigning), we build in 
204      // a generic "Memory" Absloc to aamap and use that. 
205
206      std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(Absloc(0));
207      if (i != aaMap.end()) {
208        i->second->out().setGenerator(addr.var());
209        
210        if (cond == true_()) {
211          res[i->second] = getBinaryAST(ROSEOperation::writeRepOp,
212                                        data.var(),
213                                        repeat.var());
214        }
215        else {
216          res[i->second] = getTernaryAST(ROSEOperation::writeRepOp,
217                                         data.var(),
218                                         cond.var(), 
219                                         repeat.var());
220        }
221      }
222    }
223
224    template <size_t Len>
225      void writeMemory(X86SegmentRegister,
226                       Handle<32> addr,
227                       Handle<Len> data,
228                       Handle<1> cond) {
229      std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(Absloc(0));
230      if (i != aaMap.end()) {
231        i->second->out().setGenerator(addr.var());
232        if (cond == true_()) {    
233          // Thinking about it... I think we avoid the "writeOp"
234          // because it's implicit in what we're setting; the 
235          // dereference goes on the left hand side rather than the
236          // right
237          res[i->second] = data.var();
238          /*
239          res[i->second] = getUnaryAST(ROSEOperation::writeOp,
240                                       data.var());
241          */
242        } 
243        else {
244          res[i->second] = getBinaryAST(ROSEOperation::writeOp,
245                                        data.var(),
246                                        cond.var());
247        }
248      }
249    }
250
251    // Create a representation for a Len-bit constant
252    template <size_t Len>
253      Handle<Len> number(uint64_t n) {
254      return Handle<Len>(getConstAST(n, Len));
255    }
256
257    Handle<1> true_() {
258      return Handle<1>(getConstAST(1, 1));
259    }
260
261    Handle<1> false_() {
262      return Handle<1>(getConstAST(0, 1));
263    }
264
265    // TODO FIXME - we need a "bottom".
266    Handle<1> undefined_() {
267      return Handle<1>(getBottomAST());
268    }
269
270    // If-then-else
271     
272    template <size_t Len>
273      Handle<Len> ite(Handle<1> sel, 
274                      Handle<Len> ifTrue, 
275                      Handle<Len> ifFalse) {
276      return Handle<Len>(getTernaryAST(ROSEOperation::ifOp,
277                                       sel.var(),
278                                       ifTrue.var(),
279                                       ifFalse.var()));
280    }
281
282
283    // UNARY OPERATIONS
284
285    // This is actually a ternary operation with
286    // the second parameter implicit in the
287    // template specifications...
288    // From/To specify the range of bits to 
289    // extract from the data type.
290    template<size_t From, size_t To, size_t Len> 
291      Handle<To-From> extract(Handle<Len> a) {
292      return Handle<To-From>(a.var());
293      /*
294      return Handle<To-From>(getTernaryAST(ROSEOperation::extractOp, 
295                                           a.var(),
296                                           number<Len>(From).var(),
297                                           number<Len>(To).var()));
298      */
299    }
300
301    template <size_t Len>
302      Handle<Len> invert(Handle<Len> a) {
303      return Handle<Len>(getUnaryAST(ROSEOperation::invertOp, a.var()));
304    }
305
306    template <size_t Len>
307      Handle<Len> negate(Handle<Len> a) {
308      return Handle<Len>(getUnaryAST(ROSEOperation::negateOp, a.var()));
309    }
310
311    template <size_t From, size_t To> 
312      Handle<To> signExtend(Handle<From> a) {
313      return Handle<To>(getBinaryAST(ROSEOperation::signExtendOp,
314                                     a.var(),
315                                     number<32>(To).var()));
316    }
317
318    template <size_t Len>
319      Handle<1> equalToZero(Handle<Len> a) {
320      return Handle<1>(getUnaryAST(ROSEOperation::equalToZeroOp, a.var()));
321    }
322
323    template <size_t Len>
324      Handle<Len> leastSignificantSetBit(Handle<Len> a) {
325      return Handle<Len>(getUnaryAST(ROSEOperation::LSBSetOp, a.var()));
326    }
327
328    template <size_t Len>
329      Handle<Len> mostSignificantSetBit(Handle<Len> a) {
330      return Handle<Len>(getUnaryAST(ROSEOperation::MSBSetOp, a.var()));
331    }
332
333    // BINARY OPERATIONS
334
335    template <size_t Len1, size_t Len2>
336      Handle<Len1+Len2> concat(Handle<Len1> a, Handle<Len2> b) {
337      return Handle<Len1+Len2>(getBinaryAST(ROSEOperation::concatOp, a.var(), b.var()));
338    }
339
340    template <size_t Len>
341      Handle<Len> and_(Handle<Len> a, Handle<Len> b) {
342      return Handle<Len>(getBinaryAST(ROSEOperation::andOp, a.var(), b.var()));
343    }
344
345     
346    template <size_t Len>
347      Handle<Len> or_(Handle<Len> a, Handle<Len> b) {
348      return Handle<Len>(getBinaryAST(ROSEOperation::orOp, a.var(), b.var()));
349    }
350
351    template <size_t Len>    
352      Handle<Len> xor_(Handle<Len> a, Handle<Len> b) {
353      return Handle<Len>(getBinaryAST(ROSEOperation::xorOp, a.var(), b.var()));
354    }
355     
356    template <size_t Len>    
357      Handle<Len> add(Handle<Len> a, Handle<Len> b) {
358      return Handle<Len>(getBinaryAST(ROSEOperation::addOp, a.var(), b.var()));
359    }
360
361    template <size_t Len, size_t SALen>
362      Handle<Len> rotateLeft(Handle<Len> a, Handle<SALen> b) {
363      return Handle<Len>(getBinaryAST(ROSEOperation::rotateLOp, a.var(), b.var()));
364    }
365     
366    template <size_t Len, size_t SALen>
367      Handle<Len> rotateRight(Handle<Len> a, Handle<SALen> b) {
368      return Handle<Len>(getBinaryAST(ROSEOperation::rotateROp, a.var(), b.var()));
369    }
370
371    template <size_t Len, size_t SALen>
372      Handle<Len> shiftLeft(Handle<Len> a, Handle<SALen> b) {
373      return Handle<Len>(getBinaryAST(ROSEOperation::shiftLOp, a.var(), b.var()));
374    }
375
376    template <size_t Len, size_t SALen>
377      Handle<Len> shiftRight(Handle<Len> a, Handle<SALen> b) {
378      return Handle<Len>(getBinaryAST(ROSEOperation::shiftROp, a.var(), b.var()));
379    }
380
381    template <size_t Len, size_t SALen>
382      Handle<Len> shiftRightArithmetic(Handle<Len> a, Handle<SALen> b) {
383      return Handle<Len>(getBinaryAST(ROSEOperation::shiftRArithOp, a.var(), b.var()));
384    }
385
386    template<size_t Len1, size_t Len2>
387      Handle<Len1+Len2> signedMultiply(Handle<Len1> a, Handle<Len2> b) {
388      return Handle<Len1+Len2>(getBinaryAST(ROSEOperation::sMultOp, a.var(), b.var()));
389    }
390
391    template<size_t Len1, size_t Len2>
392      Handle<Len1+Len2> unsignedMultiply(Handle<Len1> a, Handle<Len2> b) {
393      return Handle<Len1+Len2>(getBinaryAST(ROSEOperation::uMultOp, a.var(), b.var()));
394    }
395  
396    template<size_t Len1, size_t Len2>
397      Handle<Len1> signedDivide(Handle<Len1> a, Handle<Len2> b) {
398      return Handle<Len1>(getBinaryAST(ROSEOperation::sDivOp, a.var(), b.var()));
399    }
400
401    template<size_t Len1, size_t Len2>
402      Handle<Len2> signedModulo(Handle<Len1> a, Handle<Len2> b) {
403      return Handle<Len2>(getBinaryAST(ROSEOperation::sModOp, a.var(), b.var()));
404    }
405
406    template<size_t Len1, size_t Len2>    
407      Handle<Len1> unsignedDivide(Handle<Len1> a, Handle<Len2> b) {
408      return Handle<Len1>(getBinaryAST(ROSEOperation::uDivOp, a.var(), b.var()));
409    }
410
411    template<size_t Len1, size_t Len2>
412      Handle<Len2> unsignedModulo(Handle<Len1> a, Handle<Len2> b) {
413      return Handle<Len2>(getBinaryAST(ROSEOperation::sModOp, a.var(), b.var()));
414    }
415     
416    // Ternary (??) operations
417     
418    template<size_t Len>
419      Handle<Len> add3(Handle<Len> a, Handle<Len> b, Handle<1> c) {
420      return Handle<Len>(getBinaryAST(ROSEOperation::addOp,
421                                      a.var(),
422                                      getBinaryAST(ROSEOperation::addOp,
423                                                   b.var(),
424                                                   c.var())));
425    }
426     
427    template<size_t Len>
428      Handle<Len> xor3(Handle<Len> a, Handle<Len> b, Handle<Len> c) {
429      return Handle<Len>(getBinaryAST(ROSEOperation::xorOp,
430                                      a.var(),
431                                      getBinaryAST(ROSEOperation::xorOp,
432                                                   b.var(),
433                                                   c.var())));
434    }
435     
436    template<size_t Len>
437      Handle<Len> addWithCarries(Handle<Len> a, 
438                                 Handle<Len> b,
439                                 Handle<1> carryIn,
440                                 Handle<Len>& carries) {
441      Handle<Len+1> aa = Handle<Len+1>(extendByMSB<Len, Len+1>(a.var()));
442      Handle<Len+1> bb = Handle<Len+1>(extendByMSB<Len, Len+1>(b.var()));
443      Handle<Len+1> result = add3(aa, bb, carryIn);
444      carries = extract<1,Len+1>(xor3(aa, bb, result));
445      return extract<0,Len>(result);
446    }
447
448    // Misc
449     
450    void hlt() {};
451    void interrupt(uint8_t) {};
452     
453    Handle<64> rdtsc() {
454      return number<64>(0);
455    }
456
457    void startBlock(uint64_t) {}
458    void finishBlock(uint64_t) {}
459
460    Handle<32> filterIndirectJumpTarget(Handle<32> x) { return x; }
461
462    Handle<32> filterCallTarget(Handle<32> x) { return x; }
463
464    Handle<32> filterReturnTarget(Handle<32> x) { return x; }
465
466    template <size_t From, size_t To>
467      Handle<To> extendByMSB(Handle<From> a) {
468      return Handle<To>(a.var());
469      /*
470      return Handle<To>(getBinaryAST(ROSEOperation::extendMSBOp,
471                                     a.var(),
472                                     number<32>(To).var()));
473      */
474    }
475
476  private:
477    // Don't use this...
478    SymEvalPolicy();
479
480    // This is the thing we fill in ;)
481    SymEval::Result &res;
482
483    Architecture arch;
484
485    Handle<32> ip_;
486
487     
488
489    // The above is an Assignment::Ptr -> AST::Ptr map
490    // But assignments aren't very easy to deal with.
491    // So also construct a map from Abslocs
492    // to Assignments for the registers; 
493    // we use a generic "memory" absloc to handle
494    // assignments to memory.
495
496    std::map<Absloc, Assignment::Ptr> aaMap;
497
498    // Conversion functions
499    Absloc convert(X86GeneralPurposeRegister r);
500    Absloc convert(X86SegmentRegister r);
501    Absloc convert(X86Flag r);
502    AST::Ptr wrap(Absloc r) { 
503      return AbsRegionAST::create(AbsRegion(r));
504    }
505
506
507     AST::Ptr getConstAST(uint64_t n, size_t) {
508       return ConstantAST::create(n);
509     }
510                         
511     AST::Ptr getBottomAST() {
512       return BottomAST::create(false);
513     }
514                 
515     AST::Ptr getUnaryAST(ROSEOperation::Op op,
516                          AST::Ptr a) {
517       return RoseAST::create(ROSEOperation(op), a);
518     }
519
520     AST::Ptr getBinaryAST(ROSEOperation::Op op,
521                           AST::Ptr a,
522                           AST::Ptr b) {
523       return RoseAST::create(ROSEOperation(op), a, b);
524     }
525     
526     AST::Ptr getTernaryAST(ROSEOperation::Op op,
527                            AST::Ptr a,
528                            AST::Ptr b,
529                            AST::Ptr c) {
530       return RoseAST::create(ROSEOperation(op), a, b, c);
531     }
532     
533 };
534 };
535 };
536 #endif