dataflowAPI/h/SymEval.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 // Stubs for now
  32
  33 #if !defined(SymEval_h)
  34 #define SymEval_h
  35
  36 #include <map>
  37
  38 #include "Absloc.h"
  39 #include "DynAST.h"
  40
  41 #include "Graph.h"
  42 #include "util.h"
  43 #include "Node.h"
  44 #include "Edge.h"
  45
  46 class SgAsmx86Instruction;
  47 class SgAsmExpression;
  48 class SgAsmPowerpcInstruction;
  49 class SgAsmOperandList;
  50 class SgAsmx86RegisterReferenceExpression;
  51 class SgAsmPowerpcRegisterReferenceExpression;
  52
  53 namespace Dyninst {
  54
  55    namespace ParseAPI {
  56       class Function;
  57       class Block;
  58    };
  59
  60 namespace DataflowAPI {
  61
  62 // The ROSE symbolic evaluation engine wants a data type that
  63 // is template parametrized on the number of bits in the data
  64 // type. However, our ASTs don't have this, and a shared_ptr
  65 // to an AST _definitely_ doesn't have it. Instead, we use
  66 // a wrapper class (Handle) that is parametrized appropriately
  67 // and contains a shared pointer.
  68
  69 // This uses a pointer to a shared pointer. This is ordinarily a really
  70 // bad idea, but stripping the pointer part makes the compiler allocate
  71 // all available memory and crash. No idea why.
  72
  73 // Define the operations used by ROSE
  74
  75 struct Variable {
  76   DATAFLOW_EXPORT Variable() : reg(), addr(0) {};
  77   DATAFLOW_EXPORT Variable(AbsRegion r) : reg(r), addr(0) {};
  78   DATAFLOW_EXPORT Variable(AbsRegion r, Address a) : reg(r), addr(a) {};
  79
  80   DATAFLOW_EXPORT bool operator==(const Variable &rhs) const {
  81     return ((rhs.addr == addr) && (rhs.reg == reg));
  82   }
  83
  84   DATAFLOW_EXPORT bool operator<(const Variable &rhs) const {
  85     if (addr < rhs.addr) return true;
  86     if (reg < rhs.reg) return true;
  87     return false;
  88   }
  89
  90   DATAFLOW_EXPORT const std::string format() const {
  91     std::stringstream ret;
  92     ret << "V(" << reg;
  93     if (addr) ret << ":" << std::hex << addr << std::dec;
  94     ret << ")";
  95     return ret.str();
  96   }
  97
  98    AbsRegion reg;
  99    Address addr;
 100 };
 101
 102 struct Constant {
 103   DATAFLOW_EXPORT Constant() : val(0), size(0) {};
 104   DATAFLOW_EXPORT Constant(uint64_t v) : val(v), size(0) {};
 105   DATAFLOW_EXPORT Constant(uint64_t v, size_t s) : val(v), size(s) {};
 106
 107  DATAFLOW_EXPORT  bool operator==(const Constant &rhs) const {
 108     return ((rhs.val == val) && (rhs.size == size));
 109   }
 110
 111   DATAFLOW_EXPORT bool operator<(const Constant &rhs) const {
 112     if (val < rhs.val) return true;
 113     if (size < rhs.size) return true;
 114     return false;
 115   }
 116
 117   DATAFLOW_EXPORT const std::string format() const {
 118     std::stringstream ret;
 119     ret << val;
 120     if (size) {
 121     ret << ":" << size;
 122     }
 123     return ret.str();
 124   }
 125
 126    uint64_t val;
 127    size_t size;
 128 };
 129
 130 // Define the operations used by ROSE
 131
 132 struct ROSEOperation {
 133 typedef enum {
 134     nullOp,
 135     extractOp,
 136     invertOp,
 137     negateOp,
 138     signExtendOp,
 139     equalToZeroOp,
 140     generateMaskOp,
 141     LSBSetOp,
 142     MSBSetOp,
 143     concatOp,
 144     andOp,
 145     orOp,
 146     xorOp,
 147     addOp,
 148     rotateLOp,
 149     rotateROp,
 150     shiftLOp,
 151     shiftROp,
 152     shiftRArithOp,
 153     derefOp,
 154     writeRepOp,
 155     writeOp,
 156     ifOp,
 157     sMultOp,
 158     uMultOp,
 159     sDivOp,
 160     sModOp,
 161     uDivOp,
 162     uModOp,
 163     extendOp,
 164     extendMSBOp
 165 } Op;
 166
 167 DATAFLOW_EXPORT ROSEOperation(Op o) : op(o), size(0) {};
 168 DATAFLOW_EXPORT ROSEOperation(Op o, size_t s) : op(o), size(s) {};
 169
 170 DATAFLOW_EXPORT bool operator==(const ROSEOperation &rhs) const {
 171     return ((rhs.op == op) && (rhs.size == size));
 172 }
 173
 174 DATAFLOW_EXPORT const std::string format() const {
 175     std::stringstream ret;
 176     ret << "<";
 177     switch(op) {
 178     case nullOp:
 179     ret << "null";
 180     break;
 181     case extractOp:
 182     ret << "extract";
 183     break;
 184     case invertOp:
 185     ret << "invert";
 186     break;
 187     case negateOp:
 188     ret << "negate";
 189     break;
 190     case signExtendOp:
 191     ret << "signExtend";
 192     break;
 193     case equalToZeroOp:
 194     ret << "eqZero?";
 195     break;
 196     case generateMaskOp:
 197     ret << "genMask";
 198     break;
 199     case LSBSetOp:
 200     ret << "LSB?";
 201     break;
 202     case MSBSetOp:
 203     ret << "MSB?";
 204     break;
 205     case concatOp:
 206     ret << "concat";
 207     break;
 208     case andOp:
 209     ret << "and";
 210     break;
 211     case orOp:
 212     ret << "or";
 213     break;
 214     case xorOp:
 215     ret << "xor";
 216     break;
 217     case addOp:
 218     ret << "add";
 219     break;
 220     case rotateLOp:
 221     ret << "rotL";
 222     break;
 223     case rotateROp:
 224     ret << "rotR";
 225     break;
 226     case shiftLOp:
 227     ret << "shl";
 228     break;
 229     case shiftROp:
 230     ret << "shr";
 231     break;
 232     case shiftRArithOp:
 233     ret << "shrA";
 234     break;
 235     case derefOp:
 236     ret << "deref";
 237     break;
 238     case writeRepOp:
 239     ret << "writeRep";
 240     break;
 241     case writeOp:
 242     ret << "write";
 243     break;
 244     case ifOp:
 245     ret << "if";
 246     break;
 247     case sMultOp:
 248     ret << "sMult";
 249     break;
 250     case uMultOp:
 251     ret << "uMult";
 252     break;
 253     case sDivOp:
 254     ret << "sDiv";
 255     break;
 256     case sModOp:
 257     ret << "sMod";
 258     break;
 259     case uDivOp:
 260     ret << "uDiv";
 261     break;
 262     case uModOp:
 263     ret << "uMod";
 264     break;
 265     case extendOp:
 266     ret << "ext";
 267     break;
 268     case extendMSBOp:
 269     ret << "extMSB";
 270     break;
 271     default:
 272     ret << " ??? ";
 273     break;
 274     };
 275     if (size) {
 276     ret << ":" << size;
 277     }
 278     ret << ">";
 279     return ret.str();
 280 };
 281
 282 Op op;
 283 size_t size;
 284 };
 285
 286 };
 287
 288 };
 289
 290 // Get this out of the Dyninst namespace...
 291 DATAFLOW_EXPORT std::ostream &operator<<(std::ostream &os, const Dyninst::DataflowAPI::ROSEOperation &o);
 292 DATAFLOW_EXPORT std::ostream &operator<<(std::ostream &os, const Dyninst::DataflowAPI::Constant &o);
 293 DATAFLOW_EXPORT std::ostream &operator<<(std::ostream &os, const Dyninst::DataflowAPI::Variable &o);
 294
 295 namespace Dyninst {
 296
 297 namespace InstructionAPI {
 298   class Instruction;
 299 }
 300
 301 class SliceNode;
 302
 303 namespace DataflowAPI {
 304
 305 typedef std::map<Assignment::Ptr, AST::Ptr> Result_t;
 306
 307 DEF_AST_LEAF_TYPE(BottomAST, bool);
 308 DEF_AST_LEAF_TYPE(ConstantAST, Constant);
 309 DEF_AST_LEAF_TYPE(VariableAST, Variable);
 310 DEF_AST_INTERNAL_TYPE(RoseAST, ROSEOperation);
 311
 312 class SymEvalPolicy;
 313
 314 class  SymEval {
 315 public:
 316     typedef boost::shared_ptr<SliceNode> SliceNodePtr;
 317     typedef boost::shared_ptr<InstructionAPI::Instruction> InstructionPtr;
 318 public:
 319   typedef enum {
 320      FAILED,
 321      WIDEN_NODE,
 322      FAILED_TRANSLATION,
 323      SKIPPED_INPUT,
 324      SUCCESS } Retval_t;
 325
 326   // Return type: mapping AbsRegions to ASTs
 327   // We then can map Assignment::AbsRegions to
 328   // SymEval::AbsRegions and come up with the answer
 329   // static const AST::Ptr Placeholder;
 330   //
 331   // Single version: hand in an Assignment, get an AST
 332     DATAFLOW_EXPORT static std::pair<AST::Ptr, bool> expand(const Assignment::Ptr &assignment);
 333
 334   // Hand in a set of Assignments
 335   // get back a map of Assignments->ASTs
 336   // We assume the assignments are prepped in the input; whatever
 337   // they point to is discarded.
 338   DATAFLOW_EXPORT static bool expand(Result_t &res,
 339                                      std::set<InstructionPtr> &failedInsns,
 340                                      bool applyVisitors = true);
 341
 342   // Hand in a Graph (of SliceNodes, natch) and get back a Result;
 343   // prior results from the Graph
 344   // are substituted into anything that uses them.
 345   DATAFLOW_EXPORT static Retval_t expand(Dyninst::Graph::Ptr slice, DataflowAPI::Result_t &res);
 346
 347  private:
 348
 349   // Symbolically evaluate an instruction and assign
 350   // an AST representation to every written absloc
 351  static bool expandInsn(const InstructionPtr insn,
 352                          const uint64_t addr,
 353                          Result_t& res);
 354
 355  static Retval_t process(SliceNodePtr ptr, Result_t &dbase, std::set<Edge::Ptr> &skipEdges);
 356
 357  static AST::Ptr simplifyStack(AST::Ptr ast, Address addr, ParseAPI::Function *func, ParseAPI::Block *block);
 358 };
 359
 360 };
 361 };
 362
 363 #endif