symEval/h/SymEval.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 // Stubs for now
  33
  34 #if !defined(SymEval_h)
  35 #define SymEval_h
  36
  37 #include <map>
  38
  39 #include "Instruction.h"
  40 #include "BinaryFunction.h"
  41 #include "Dereference.h"
  42 #include "Immediate.h"
  43 #include "Absloc.h"
  44 #include "AST.h"
  45
  46 #include "slicing.h"
  47
  48 #include "external/rose/rose-compat.h"
  49
  50 #include "Graph.h"
  51
  52 class SgAsmx86Instruction;
  53 class SgAsmExpression;
  54
  55 namespace Dyninst {
  56 namespace SymbolicEvaluation {
  57
  58 // The ROSE symbolic evaluation engine wants a data type that
  59 // is template parametrized on the number of bits in the data
  60 // type. However, our ASTs don't have this, and a shared_ptr
  61 // to an AST _definitely_ doesn't have it. Instead, we use
  62 // a wrapper class (Handle) that is parametrized appropriately
  63 // and contains a shared pointer.
  64
  65 // This uses a pointer to a shared pointer. This is ordinarily a really
  66 // bad idea, but stripping the pointer part makes the compiler allocate
  67 // all available memory and crash. No idea why.
  68
  69 // Define the operations used by ROSE
  70
  71 struct ROSEOperation {
  72   typedef enum {
  73     nullOp,
  74     extractOp,
  75     invertOp,
  76     negateOp,
  77     signExtendOp,
  78     equalToZeroOp,
  79     generateMaskOp,
  80     LSBSetOp,
  81     MSBSetOp,
  82     concatOp,
  83     andOp,
  84     orOp,
  85     xorOp,
  86     addOp,
  87     rotateLOp,
  88     rotateROp,
  89     shiftLOp,
  90     shiftROp,
  91     shiftRArithOp,
  92     derefOp,
  93     writeRepOp,
  94     writeOp,
  95     ifOp,
  96     sMultOp,
  97     uMultOp,
  98     sDivOp,
  99     sModOp,
 100     uDivOp,
 101     uModOp,
 102     extendOp,
 103     extendMSBOp
 104   } Op;
 105
 106   ROSEOperation(Op o) : op(o) {};
 107
 108   bool operator==(const ROSEOperation &rhs) const {
 109     return (rhs.op == op);
 110   }
 111
 112   const std::string format() const {
 113     switch(op) {
 114     case nullOp:
 115       return "<null>";
 116     case extractOp:
 117       return "<extract>";
 118     case invertOp:
 119       return "<invert>";
 120     case negateOp:
 121       return "<negate>";
 122     case signExtendOp:
 123       return "<signExtend>";
 124     case equalToZeroOp:
 125       return "<eqZero?>";
 126     case generateMaskOp:
 127       return "<genMask>";
 128     case LSBSetOp:
 129       return "<LSB?>";
 130     case MSBSetOp:
 131       return "<MSB?>";
 132     case concatOp:
 133       return "<concat>";
 134     case andOp:
 135       return "<and>";
 136     case orOp:
 137       return "<or>";
 138     case xorOp:
 139       return "<xor>";
 140     case addOp:
 141       return "<add>";
 142     case rotateLOp:
 143       return "<rotL>";
 144     case rotateROp:
 145       return "<rotR>";
 146     case shiftLOp:
 147       return "<shl>";
 148     case shiftROp:
 149       return "<shr>";
 150     case shiftRArithOp:
 151       return "<shrA>";
 152     case derefOp:
 153       return "<deref>";
 154     case writeRepOp:
 155       return "<writeRep>";
 156     case writeOp:
 157       return "<write>";
 158     case ifOp:
 159       return "<if>";
 160     case sMultOp:
 161       return "<sMult>";
 162     case uMultOp:
 163       return "<uMult>";
 164     case sDivOp:
 165       return "<sDiv>";
 166     case sModOp:
 167       return "<sMod>";
 168     case uDivOp:
 169       return "<uDiv>";
 170     case uModOp:
 171       return "<uMod>";
 172     case extendOp:
 173       return "<ext>";
 174     case extendMSBOp:
 175       return "<extMSB>";
 176     default:
 177       return "< ??? >";
 178     };
 179   };
 180
 181   Op op;
 182 };
 183
 184 };
 185
 186 };
 187
 188 // Get this out of the Dyninst namespace...
 189 std::ostream &operator<<(std::ostream &os, const Dyninst::SymbolicEvaluation::ROSEOperation &o);
 190
 191 namespace Dyninst {
 192
 193 namespace SymbolicEvaluation {
 194
 195 DEF_AST_LEAF_TYPE(BottomAST, bool);
 196 DEF_AST_LEAF_TYPE(ConstantAST, uint64_t);
 197 DEF_AST_LEAF_TYPE(AbsRegionAST, AbsRegion);
 198 DEF_AST_INTERNAL_TYPE(RoseAST, ROSEOperation);
 199
 200 class SymEval {
 201  public:
 202   // Return type: mapping AbsRegions to ASTs
 203   // We then can map Assignment::AbsRegions to
 204   // SymEval::AbsRegions and come up with the answer
 205
 206   typedef std::map<Assignment::Ptr, AST::Ptr> Result;
 207   static const AST::Ptr Placeholder;
 208
 209   // Single version: hand in an Assignment, get an AST
 210   static AST::Ptr expand(const Assignment::Ptr &assignment);
 211
 212   // Hand in a set of Assignments
 213   // get back a map of Assignments->ASTs
 214   // We assume the assignments are prepped in the input; whatever
 215   // they point to is discarded.
 216   static void expand(Result &res);
 217
 218   // Hand in a Graph (of AssignNodes, natch) and get back a Result;
 219   // prior results from the Graph
 220   // are substituted into anything that uses them.
 221   static void expand(Graph::Ptr slice, Result &res);
 222
 223  private:
 224   static void process(AssignNode::Ptr, SymEval::Result &res);
 225
 226   static SgAsmx86Instruction convert(const InstructionAPI::Instruction::Ptr &insn, uint64_t addr);
 227   static X86InstructionKind convert(entryID opcode);
 228   static SgAsmExpression *convert(const InstructionAPI::Operand &operand);
 229   static SgAsmExpression *convert(const InstructionAPI::Expression::Ptr expression);
 230
 231   // Symbolically evaluate an instruction and assign
 232   // an AST representation to every written absloc
 233   static void expandInsn(const InstructionAPI::Instruction::Ptr insn,
 234                          const uint64_t addr,
 235                          Result &res);
 236
 237   friend class ExpressionConversionVisitor;
 238 };
 239
 240 class ExpressionConversionVisitor : public InstructionAPI::Visitor {
 241  public:
 242     ExpressionConversionVisitor() { roseExpression = NULL; }
 243
 244     SgAsmExpression *getRoseExpression() { return roseExpression; }
 245
 246     virtual void visit(InstructionAPI::BinaryFunction *binfunc);
 247     virtual void visit(InstructionAPI::Immediate *immed);
 248     virtual void visit(InstructionAPI::RegisterAST *regast);
 249     virtual void visit(InstructionAPI::Dereference *deref);
 250
 251  private:
 252     SgAsmExpression *roseExpression;
 253 };
 254
 255 };
 256 };
 257
 258 #endif