Merge branch 'master' into devel
[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 "../h/Absloc.h"
59
60 #include <iostream>
61 #include <fstream>
62 #include <sstream>
63
64 #if !defined(_MSC_VER)
65 #include <stdint.h>
66 #else
67 #include "external/stdint-win.h"
68 #endif
69
70
71 #include "../rose/SgAsmx86Instruction.h"
72 #include "../rose/SgAsmPowerpcInstruction.h"
73 // Also need ROSE header files... argh. 
74
75 // For typedefs
76 #include "../h/SymEval.h"
77
78 namespace Dyninst {
79
80 namespace SymbolicEvaluation {
81
82 // The ROSE symbolic evaluation engine wants a data type that
83 // is template parametrized on the number of bits in the data
84 // type. However, our ASTs don't have this, and a shared_ptr
85 // to an AST _definitely_ doesn't have it. Instead, we use
86 // a wrapper class (Handle) that is parametrized appropriately
87 // and contains a shared pointer. 
88
89 // This uses a pointer to a shared pointer. This is ordinarily a really
90 // bad idea, but stripping the pointer part makes the compiler allocate
91 // all available memory and crash. No idea why. 
92
93
94
95 template <size_t Len>
96 struct Handle {
97   AST::Ptr *v_;
98   Handle() : v_(NULL) {
99     assert(0);
100   };
101   Handle(AST::Ptr v) {
102     assert(v);
103     v_ = new AST::Ptr(v);
104   };
105   Handle(const Handle &rhs) {
106     v_ = new AST::Ptr(rhs.var());
107   }
108   Handle operator=(const Handle &rhs) {
109     if (v_) delete v_;
110     v_ = new AST::Ptr(rhs.var());
111     return  *this;
112   }
113     ~Handle() { if (v_) delete v_; };
114   
115   template <size_t Len2>
116   bool operator==(const Handle<Len2> &rhs) {
117     return ((Len == Len2) && (*(var()) == *(rhs.var())));
118   }
119
120   AST::Ptr var() const { 
121     assert(v_); return *v_;
122   }
123   
124   //operator AST::Ptr() const { return *var; }
125   //AST::Ptr operator->() const { return *var; }
126 };
127
128
129  class SymEvalPolicy {
130  public:
131
132      SymEvalPolicy(Result_t &r,
133                  Address addr,
134                  Dyninst::Architecture a);
135
136    ~SymEvalPolicy() {};
137   
138    void startInstruction(SgAsmx86Instruction *);
139    void startInstruction(SgAsmPowerpcInstruction *);
140
141    void finishInstruction(SgAsmx86Instruction *);
142    void finishInstruction(SgAsmPowerpcInstruction *);
143     
144    // Policy classes must implement the following methods:
145    Handle<32> readGPR(X86GeneralPurposeRegister r) {
146      return Handle<32>(wrap(convert(r)));
147    }
148     
149    void writeGPR(X86GeneralPurposeRegister r, Handle<32> value) {
150      std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(convert(r));
151      if (i != aaMap.end()) {
152        res[i->second] = value.var();
153      } 
154      else {
155        /*
156        std::cerr << "Warning: discarding write to GPR " << convert(r).format() << std::endl;
157        for (std::map<Absloc, Assignment::Ptr>::iterator foozle = aaMap.begin();
158             foozle != aaMap.end(); ++foozle) {
159          std::cerr << "\t" << foozle->first.format() << std::endl;
160        }
161        */
162      }
163    }
164    
165    Handle<32> readGPR(unsigned int r) {
166        return Handle<32>(wrap(convert(powerpc_regclass_gpr, r)));
167    }
168
169    void writeGPR(unsigned int r, Handle<32> value) {
170        std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(convert(powerpc_regclass_gpr, r));
171        if (i != aaMap.end()) {
172            res[i->second] = value.var();
173        }
174    }
175    Handle<32> readSPR(unsigned int r) {
176         return Handle<32>(wrap(convert(powerpc_regclass_spr, r)));
177     }
178     void writeSPR(unsigned int r, Handle<32> value) {
179         std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(convert(powerpc_regclass_spr, r));
180         if (i != aaMap.end()) {
181             res[i->second] = value.var();
182         }
183     }
184     Handle<4> readCRField(unsigned int field) {
185         return Handle<4>(wrap(convert(powerpc_regclass_cr, field)));
186     }
187     Handle<32> readCR() {
188         return Handle<32>(wrap(convert(powerpc_regclass_cr, (unsigned int)-1)));
189     }
190     void writeCRField(unsigned int field, Handle<4> value) {
191         std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(convert(powerpc_regclass_cr, field));
192         if (i != aaMap.end()) {
193             res[i->second] = value.var();
194         }
195     }
196    Handle<16> readSegreg(X86SegmentRegister r) {
197      return Handle<16>(wrap(convert(r)));
198    }
199     void systemCall(unsigned char value)
200     {
201         fprintf(stderr, "WARNING: syscall %d detected; unhandled by semantics!\n", (unsigned int)(value));
202     }
203    void writeSegreg(X86SegmentRegister r, Handle<16> value) {
204      std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(convert(r));
205      if (i != aaMap.end()) {
206        res[i->second] = value.var();
207      }
208      // Otherwise we don't care. Annoying that we 
209      // had to expand this register...
210    }
211     
212    Handle<32> readIP() { 
213      return ip_;
214    }
215     
216    void writeIP(Handle<32> value) {
217      // Always care about the IP...
218      std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(Absloc::makePC(arch));
219      if (i != aaMap.end()) {
220        res[i->second] = value.var();
221      }
222      ip_ = value;
223      // Otherwise we don't care. Annoying that we 
224      // had to expand this register...
225    } 
226     
227    Handle<1> readFlag(X86Flag f) {
228      return Handle<1>(wrap(convert(f)));
229    }
230     
231    void writeFlag(X86Flag f, Handle<1> value) {
232      std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(convert(f));
233      if (i != aaMap.end()) {
234        res[i->second] = value.var();
235      }
236      // Otherwise we don't care. Annoying that we 
237      // had to expand this register...
238    }
239
240    // Len here is the number of bits read, which we'll
241    // turn into an argument of the ROSEOperation. 
242     
243    template <size_t Len>
244      Handle<Len> readMemory(X86SegmentRegister /*segreg*/,
245                             Handle<32> addr,
246                             Handle<1> cond) {
247      if (cond == true_()) {
248        return Handle<Len>(getUnaryAST(ROSEOperation::derefOp,
249                                       addr.var(),
250                                       Len));
251      }
252      else {
253        return Handle<Len>(getBinaryAST(ROSEOperation::derefOp,
254                                        addr.var(),
255                                        cond.var(),
256                                        Len));
257      }
258    }
259         
260    template <size_t Len>
261      Handle<Len> readMemory(Handle<32> addr,
262                             Handle<1> cond) {
263     return Handle<Len>(getBinaryAST(ROSEOperation::derefOp,
264                                     addr.var(),
265                                     cond.var(),
266                                     Len));
267      }
268      template <size_t Len>
269      void writeMemory(X86SegmentRegister,
270                       Handle<32> addr,
271                       Handle<Len> data,
272                       Handle<32> repeat,
273                       Handle<1> cond) {
274      // We can only write memory once per instruction. Therefore, 
275      // instead of sweating what we're actually being handed (or
276      // what AbsRegion we're actually assigning), we build in 
277      // a generic "Memory" Absloc to aamap and use that. 
278
279      std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(Absloc(0));
280      if (i != aaMap.end()) {
281        i->second->out().setGenerator(addr.var());
282        i->second->out().setSize(Len);
283        
284        if (cond == true_()) {
285          res[i->second] = getBinaryAST(ROSEOperation::writeRepOp,
286                                        data.var(),
287                                        repeat.var());
288        }
289        else {
290          res[i->second] = getTernaryAST(ROSEOperation::writeRepOp,
291                                         data.var(),
292                                         cond.var(), 
293                                         repeat.var());
294        }
295      }
296    }
297
298    template <size_t Len>
299    void writeMemory(Handle<32> addr,
300                     Handle<Len> data,
301                     Handle<1> cond) {
302         std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(Absloc(0));
303         if (i != aaMap.end()) {
304             i->second->out().setGenerator(addr.var());
305             i->second->out().setSize(Len);
306             if (cond == true_()) {
307                 // Thinking about it... I think we avoid the "writeOp"
308                 // because it's implicit in what we're setting; the 
309                 // dereference goes on the left hand side rather than the
310                 // right
311                 res[i->second] = data.var();
312             }
313             else {
314                 res[i->second] = getBinaryAST(ROSEOperation::writeOp,
315                         data.var(),
316                         cond.var());
317             }
318         }
319     }
320
321    
322    template <size_t Len>
323      void writeMemory(X86SegmentRegister,
324                       Handle<32> addr,
325                       Handle<Len> data,
326                       Handle<1> cond) {
327      std::map<Absloc, Assignment::Ptr>::iterator i = aaMap.find(Absloc(0));
328      if (i != aaMap.end()) {
329        i->second->out().setGenerator(addr.var());
330        i->second->out().setSize(Len);
331        if (cond == true_()) {    
332          // Thinking about it... I think we avoid the "writeOp"
333          // because it's implicit in what we're setting; the 
334          // dereference goes on the left hand side rather than the
335          // right
336          res[i->second] = data.var();
337          /*
338          res[i->second] = getUnaryAST(ROSEOperation::writeOp,
339                                       data.var());
340          */
341        } 
342        else {
343          res[i->second] = getBinaryAST(ROSEOperation::writeOp,
344                                        data.var(),
345                                        cond.var());
346        }
347      }
348    }
349
350    // Create a representation for a Len-bit constant
351    template <size_t Len>
352      Handle<Len> number(uint64_t n) {
353      return Handle<Len>(getConstAST(n, Len));
354    }
355
356    Handle<1> true_() {
357      return Handle<1>(getConstAST(1, 1));
358    }
359
360    Handle<1> false_() {
361      return Handle<1>(getConstAST(0, 1));
362    }
363
364    // TODO FIXME - we need a "bottom".
365    Handle<1> undefined_() {
366      return Handle<1>(getBottomAST());
367    }
368
369    // If-then-else
370     
371    template <size_t Len>
372      Handle<Len> ite(Handle<1> sel, 
373                      Handle<Len> ifTrue, 
374                      Handle<Len> ifFalse) {
375      return Handle<Len>(getTernaryAST(ROSEOperation::ifOp,
376                                       sel.var(),
377                                       ifTrue.var(),
378                                       ifFalse.var()));
379    }
380
381
382    // UNARY OPERATIONS
383
384    // This is actually a ternary operation with
385    // the second parameter implicit in the
386    // template specifications...
387    // From/To specify the range of bits to 
388    // extract from the data type.
389    template<size_t From, size_t To, size_t Len> 
390      Handle<To-From> extract(Handle<Len> a) {
391      // return Handle<To-From>(a.var());
392      return Handle<To-From>(getTernaryAST(ROSEOperation::extractOp, 
393                                           a.var(),
394                                           number<Len>(From).var(),
395                                           number<Len>(To).var(),
396                                           To-From));
397    }
398
399    template <size_t Len>
400      Handle<Len> invert(Handle<Len> a) {
401      return Handle<Len>(getUnaryAST(ROSEOperation::invertOp, a.var()));
402    }
403
404    template <size_t Len>
405      Handle<Len> negate(Handle<Len> a) {
406      return Handle<Len>(getUnaryAST(ROSEOperation::negateOp, a.var()));
407    }
408
409    template <size_t From, size_t To> 
410      Handle<To> signExtend(Handle<From> a) {
411      return Handle<To>(getBinaryAST(ROSEOperation::signExtendOp,
412                                     a.var(),
413                                     number<32>(To).var()));
414    }
415
416    template <size_t Len>
417      Handle<1> equalToZero(Handle<Len> a) {
418      return Handle<1>(getUnaryAST(ROSEOperation::equalToZeroOp, a.var()));
419    }
420
421    template <size_t Len>
422      Handle<Len> leastSignificantSetBit(Handle<Len> a) {
423      return Handle<Len>(getUnaryAST(ROSEOperation::LSBSetOp, a.var()));
424    }
425
426    template <size_t Len>
427      Handle<Len> mostSignificantSetBit(Handle<Len> a) {
428      return Handle<Len>(getUnaryAST(ROSEOperation::MSBSetOp, a.var()));
429    }
430
431    // BINARY OPERATIONS
432
433    template <size_t Len1, size_t Len2>
434      Handle<Len1+Len2> concat(Handle<Len1> a, Handle<Len2> b) {
435      return Handle<Len1+Len2>(getBinaryAST(ROSEOperation::concatOp, a.var(), b.var(), Len1+Len2));
436    }
437
438    template <size_t Len>
439      Handle<Len> and_(Handle<Len> a, Handle<Len> b) {
440      return Handle<Len>(getBinaryAST(ROSEOperation::andOp, a.var(), b.var()));
441    }
442
443     
444    template <size_t Len>
445      Handle<Len> or_(Handle<Len> a, Handle<Len> b) {
446      return Handle<Len>(getBinaryAST(ROSEOperation::orOp, a.var(), b.var()));
447    }
448
449    template <size_t Len>    
450      Handle<Len> xor_(Handle<Len> a, Handle<Len> b) {
451      return Handle<Len>(getBinaryAST(ROSEOperation::xorOp, a.var(), b.var()));
452    }
453     
454    template <size_t Len>    
455      Handle<Len> add(Handle<Len> a, Handle<Len> b) {
456      return Handle<Len>(getBinaryAST(ROSEOperation::addOp, a.var(), b.var()));
457    }
458
459    template <size_t Len, size_t SALen>
460      Handle<Len> rotateLeft(Handle<Len> a, Handle<SALen> b) {
461      return Handle<Len>(getBinaryAST(ROSEOperation::rotateLOp, a.var(), b.var()));
462    }
463     
464    template <size_t Len, size_t SALen>
465      Handle<Len> rotateRight(Handle<Len> a, Handle<SALen> b) {
466      return Handle<Len>(getBinaryAST(ROSEOperation::rotateROp, a.var(), b.var()));
467    }
468
469    template <size_t Len, size_t SALen>
470      Handle<Len> shiftLeft(Handle<Len> a, Handle<SALen> b) {
471      return Handle<Len>(getBinaryAST(ROSEOperation::shiftLOp, a.var(), b.var()));
472    }
473
474    template <size_t Len, size_t SALen>
475      Handle<Len> shiftRight(Handle<Len> a, Handle<SALen> b) {
476      return Handle<Len>(getBinaryAST(ROSEOperation::shiftROp, a.var(), b.var()));
477    }
478
479    template <size_t Len, size_t SALen>
480      Handle<Len> shiftRightArithmetic(Handle<Len> a, Handle<SALen> b) {
481      return Handle<Len>(getBinaryAST(ROSEOperation::shiftRArithOp, a.var(), b.var()));
482    }
483
484    template<size_t Len1, size_t Len2>
485      Handle<Len1+Len2> signedMultiply(Handle<Len1> a, Handle<Len2> b) {
486      return Handle<Len1+Len2>(getBinaryAST(ROSEOperation::sMultOp, a.var(), b.var()));
487    }
488
489    template<size_t Len1, size_t Len2>
490      Handle<Len1+Len2> unsignedMultiply(Handle<Len1> a, Handle<Len2> b) {
491      return Handle<Len1+Len2>(getBinaryAST(ROSEOperation::uMultOp, a.var(), b.var()));
492    }
493  
494    template<size_t Len1, size_t Len2>
495      Handle<Len1> signedDivide(Handle<Len1> a, Handle<Len2> b) {
496      return Handle<Len1>(getBinaryAST(ROSEOperation::sDivOp, a.var(), b.var()));
497    }
498
499    template<size_t Len1, size_t Len2>
500      Handle<Len2> signedModulo(Handle<Len1> a, Handle<Len2> b) {
501      return Handle<Len2>(getBinaryAST(ROSEOperation::sModOp, a.var(), b.var()));
502    }
503
504    template<size_t Len1, size_t Len2>    
505      Handle<Len1> unsignedDivide(Handle<Len1> a, Handle<Len2> b) {
506      return Handle<Len1>(getBinaryAST(ROSEOperation::uDivOp, a.var(), b.var()));
507    }
508
509    template<size_t Len1, size_t Len2>
510      Handle<Len2> unsignedModulo(Handle<Len1> a, Handle<Len2> b) {
511      return Handle<Len2>(getBinaryAST(ROSEOperation::sModOp, a.var(), b.var()));
512    }
513     
514    // Ternary (??) operations
515     
516    template<size_t Len>
517      Handle<Len> add3(Handle<Len> a, Handle<Len> b, Handle<1> c) {
518      return Handle<Len>(getBinaryAST(ROSEOperation::addOp,
519                                      a.var(),
520                                      getBinaryAST(ROSEOperation::addOp,
521                                                   b.var(),
522                                                   c.var())));
523    }
524     
525    template<size_t Len>
526      Handle<Len> xor3(Handle<Len> a, Handle<Len> b, Handle<Len> c) {
527      return Handle<Len>(getBinaryAST(ROSEOperation::xorOp,
528                                      a.var(),
529                                      getBinaryAST(ROSEOperation::xorOp,
530                                                   b.var(),
531                                                   c.var())));
532    }
533     
534    template<size_t Len>
535      Handle<Len> addWithCarries(Handle<Len> a, 
536                                 Handle<Len> b,
537                                 Handle<1> carryIn,
538                                 Handle<Len>& carries) {
539      Handle<Len+1> aa = Handle<Len+1>(extendByMSB<Len, Len+1>(a.var()));
540      Handle<Len+1> bb = Handle<Len+1>(extendByMSB<Len, Len+1>(b.var()));
541      Handle<Len+1> result = add3(aa, bb, carryIn);
542      carries = extract<1,Len+1>(xor3(aa, bb, result));
543      return extract<0,Len>(result);
544    }
545
546    // Misc
547     
548    void hlt() {};
549    void interrupt(uint8_t) {};
550     
551    Handle<64> rdtsc() {
552      return number<64>(0);
553    }
554
555    void startBlock(uint64_t) {}
556    void finishBlock(uint64_t) {}
557
558    Handle<32> filterIndirectJumpTarget(Handle<32> x) { return x; }
559
560    Handle<32> filterCallTarget(Handle<32> x) { return x; }
561
562    Handle<32> filterReturnTarget(Handle<32> x) { return x; }
563
564    template <size_t From, size_t To>
565      Handle<To> extendByMSB(Handle<From> a) {
566      //return Handle<To>(a.var());
567      return Handle<To>(getBinaryAST(ROSEOperation::extendMSBOp,
568                                     a.var(),
569                                     number<32>(To).var()));
570    }
571
572  private:
573    // Don't use this...
574    SymEvalPolicy();
575
576    // This is the thing we fill in ;)
577    Result_t &res;
578
579    Architecture arch;
580    Address addr;
581
582    Handle<32> ip_;
583
584     
585
586    // The above is an Assignment::Ptr -> AST::Ptr map
587    // But assignments aren't very easy to deal with.
588    // So also construct a map from Abslocs
589    // to Assignments for the registers; 
590    // we use a generic "memory" absloc to handle
591    // assignments to memory.
592
593    std::map<Absloc, Assignment::Ptr> aaMap;
594
595    // Conversion functions
596    Absloc convert(X86GeneralPurposeRegister r);
597    Absloc convert(X86SegmentRegister r);
598    Absloc convert(X86Flag r);
599    AST::Ptr wrap(Absloc r) {
600      return VariableAST::create(Variable(AbsRegion(r), addr));
601    }
602    Absloc convert(PowerpcRegisterClass c, int n);
603
604
605     AST::Ptr getConstAST(uint64_t n, size_t s) {
606       return ConstantAST::create(Constant(n, s));
607     }
608                         
609     AST::Ptr getBottomAST() {
610       return BottomAST::create(false);
611     }
612                 
613     AST::Ptr getUnaryAST(ROSEOperation::Op op,
614                          AST::Ptr a,
615                          size_t s = 0) {
616       return RoseAST::create(ROSEOperation(op, s), a);
617     }
618
619     AST::Ptr getBinaryAST(ROSEOperation::Op op,
620                           AST::Ptr a,
621                           AST::Ptr b,
622                           size_t s = 0) {
623       return RoseAST::create(ROSEOperation(op, s), a, b);
624     }
625     
626     AST::Ptr getTernaryAST(ROSEOperation::Op op,
627                            AST::Ptr a,
628                            AST::Ptr b,
629                            AST::Ptr c,
630                            size_t s = 0) {
631       return RoseAST::create(ROSEOperation(op, s), a, b, c);
632     }    
633 };
634 };
635 };
636 #endif