klee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
ExecutorUtil.cpp
Go to the documentation of this file.
1 //===-- ExecutorUtil.cpp --------------------------------------------------===//
2 //
3 // The KLEE Symbolic Virtual Machine
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "Executor.h"
11 
12 #include "Context.h"
13 
14 #include "klee/Expr.h"
15 #include "klee/Interpreter.h"
16 #include "klee/Solver.h"
17 
18 #include "klee/Config/Version.h"
20 
22 
23 #if LLVM_VERSION_CODE >= LLVM_VERSION(3, 3)
24 #include "llvm/IR/Function.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/Module.h"
28 #include "llvm/IR/DataLayout.h"
29 #else
30 #include "llvm/Constants.h"
31 #include "llvm/Function.h"
32 #include "llvm/Instructions.h"
33 #include "llvm/Module.h"
34 #if LLVM_VERSION_CODE <= LLVM_VERSION(3, 1)
35 #include "llvm/Target/TargetData.h"
36 #else
37 #include "llvm/DataLayout.h"
38 #endif
39 #endif
40 
41 #include "llvm/Support/CallSite.h"
42 
43 
44 #include <cassert>
45 
46 using namespace klee;
47 using namespace llvm;
48 
49 namespace klee {
50 
51  ref<ConstantExpr> Executor::evalConstantExpr(const llvm::ConstantExpr *ce) {
52  LLVM_TYPE_Q llvm::Type *type = ce->getType();
53 
54  ref<ConstantExpr> op1(0), op2(0), op3(0);
55  int numOperands = ce->getNumOperands();
56 
57  if (numOperands > 0) op1 = evalConstant(ce->getOperand(0));
58  if (numOperands > 1) op2 = evalConstant(ce->getOperand(1));
59  if (numOperands > 2) op3 = evalConstant(ce->getOperand(2));
60 
61  switch (ce->getOpcode()) {
62  default :
63  ce->dump();
64  llvm::errs() << "error: unknown ConstantExpr type\n"
65  << "opcode: " << ce->getOpcode() << "\n";
66  abort();
67 
68  case Instruction::Trunc:
69  return op1->Extract(0, getWidthForLLVMType(type));
70  case Instruction::ZExt: return op1->ZExt(getWidthForLLVMType(type));
71  case Instruction::SExt: return op1->SExt(getWidthForLLVMType(type));
72  case Instruction::Add: return op1->Add(op2);
73  case Instruction::Sub: return op1->Sub(op2);
74  case Instruction::Mul: return op1->Mul(op2);
75  case Instruction::SDiv: return op1->SDiv(op2);
76  case Instruction::UDiv: return op1->UDiv(op2);
77  case Instruction::SRem: return op1->SRem(op2);
78  case Instruction::URem: return op1->URem(op2);
79  case Instruction::And: return op1->And(op2);
80  case Instruction::Or: return op1->Or(op2);
81  case Instruction::Xor: return op1->Xor(op2);
82  case Instruction::Shl: return op1->Shl(op2);
83  case Instruction::LShr: return op1->LShr(op2);
84  case Instruction::AShr: return op1->AShr(op2);
85  case Instruction::BitCast: return op1;
86 
87  case Instruction::IntToPtr:
88  return op1->ZExt(getWidthForLLVMType(type));
89 
90  case Instruction::PtrToInt:
91  return op1->ZExt(getWidthForLLVMType(type));
92 
93  case Instruction::GetElementPtr: {
94  ref<ConstantExpr> base = op1->ZExt(Context::get().getPointerWidth());
95 
96  for (gep_type_iterator ii = gep_type_begin(ce), ie = gep_type_end(ce);
97  ii != ie; ++ii) {
98  ref<ConstantExpr> addend =
99  ConstantExpr::alloc(0, Context::get().getPointerWidth());
100 
101  if (LLVM_TYPE_Q StructType *st = dyn_cast<StructType>(*ii)) {
102  const StructLayout *sl = kmodule->targetData->getStructLayout(st);
103  const ConstantInt *ci = cast<ConstantInt>(ii.getOperand());
104 
105  addend = ConstantExpr::alloc(sl->getElementOffset((unsigned)
106  ci->getZExtValue()),
108  } else {
109  const SequentialType *set = cast<SequentialType>(*ii);
110  ref<ConstantExpr> index =
111  evalConstant(cast<Constant>(ii.getOperand()));
112  unsigned elementSize =
113  kmodule->targetData->getTypeStoreSize(set->getElementType());
114 
115  index = index->ZExt(Context::get().getPointerWidth());
116  addend = index->Mul(ConstantExpr::alloc(elementSize,
117  Context::get().getPointerWidth()));
118  }
119 
120  base = base->Add(addend);
121  }
122 
123  return base;
124  }
125 
126  case Instruction::ICmp: {
127  switch(ce->getPredicate()) {
128  default: assert(0 && "unhandled ICmp predicate");
129  case ICmpInst::ICMP_EQ: return op1->Eq(op2);
130  case ICmpInst::ICMP_NE: return op1->Ne(op2);
131  case ICmpInst::ICMP_UGT: return op1->Ugt(op2);
132  case ICmpInst::ICMP_UGE: return op1->Uge(op2);
133  case ICmpInst::ICMP_ULT: return op1->Ult(op2);
134  case ICmpInst::ICMP_ULE: return op1->Ule(op2);
135  case ICmpInst::ICMP_SGT: return op1->Sgt(op2);
136  case ICmpInst::ICMP_SGE: return op1->Sge(op2);
137  case ICmpInst::ICMP_SLT: return op1->Slt(op2);
138  case ICmpInst::ICMP_SLE: return op1->Sle(op2);
139  }
140  }
141 
142  case Instruction::Select:
143  return op1->isTrue() ? op2 : op3;
144 
145  case Instruction::FAdd:
146  case Instruction::FSub:
147  case Instruction::FMul:
148  case Instruction::FDiv:
149  case Instruction::FRem:
150  case Instruction::FPTrunc:
151  case Instruction::FPExt:
152  case Instruction::UIToFP:
153  case Instruction::SIToFP:
154  case Instruction::FPToUI:
155  case Instruction::FPToSI:
156  case Instruction::FCmp:
157  assert(0 && "floating point ConstantExprs unsupported");
158  }
159  }
160 
161 }
ref< ConstantExpr > Mul(const ref< ConstantExpr > &RHS)
Definition: Expr.cpp:388
gep_type_iterator gep_type_end(const llvm::User *GEP)
Expr::Width getPointerWidth() const
Definition: Context.h:40
static const Context & get()
get - Return the global singleton instance of the Context.
Definition: Context.cpp:35
#define LLVM_TYPE_Q
Definition: Version.h:21
static ref< ConstantExpr > alloc(const llvm::APInt &v)
Definition: Expr.h:398
gep_type_iterator gep_type_begin(const llvm::User *GEP)
ref< klee::ConstantExpr > evalConstantExpr(const llvm::ConstantExpr *ce)
void dump() const
dump - Print the expression to stderr.
Definition: Expr.cpp:313
ref< ConstantExpr > ZExt(Width W)
Definition: Expr.cpp:368
ref< ConstantExpr > Add(const ref< ConstantExpr > &RHS)
Definition: Expr.cpp:376