klee
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Checks.cpp
Go to the documentation of this file.
1 //===-- Checks.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 "Passes.h"
11 
12 #include "klee/Config/Version.h"
13 
14 #if LLVM_VERSION_CODE >= LLVM_VERSION(3, 3)
15 #include "llvm/IR/Constants.h"
16 #include "llvm/IR/DerivedTypes.h"
17 #include "llvm/IR/Function.h"
18 #include "llvm/IR/InstrTypes.h"
19 #include "llvm/IR/Instruction.h"
20 #include "llvm/IR/Instructions.h"
21 #include "llvm/IR/IntrinsicInst.h"
22 #include "llvm/IR/Module.h"
23 #include "llvm/IR/LLVMContext.h"
24 #include "llvm/IR/Type.h"
25 #include "llvm/IR/DataLayout.h"
26 #else
27 #include "llvm/Constants.h"
28 #include "llvm/DerivedTypes.h"
29 #include "llvm/Function.h"
30 #include "llvm/InstrTypes.h"
31 #include "llvm/Instruction.h"
32 #include "llvm/Instructions.h"
33 #include "llvm/IntrinsicInst.h"
34 #include "llvm/Module.h"
35 #include "llvm/Type.h"
36 
37 #include "llvm/LLVMContext.h"
38 
39 #if LLVM_VERSION_CODE <= LLVM_VERSION(3, 1)
40 #include "llvm/Target/TargetData.h"
41 #else
42 #include "llvm/DataLayout.h"
43 #endif
44 #endif
45 #include "llvm/Pass.h"
46 #include "llvm/Transforms/Scalar.h"
47 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
48 #include "llvm/Support/CallSite.h"
49 
50 using namespace llvm;
51 using namespace klee;
52 
53 char DivCheckPass::ID;
54 
55 bool DivCheckPass::runOnModule(Module &M) {
56  Function *divZeroCheckFunction = 0;
57 
58  bool moduleChanged = false;
59 
60  for (Module::iterator f = M.begin(), fe = M.end(); f != fe; ++f) {
61  for (Function::iterator b = f->begin(), be = f->end(); b != be; ++b) {
62  for (BasicBlock::iterator i = b->begin(), ie = b->end(); i != ie; ++i) {
63  if (BinaryOperator* binOp = dyn_cast<BinaryOperator>(i)) {
64  // find all [s|u][div|mod] instructions
65  Instruction::BinaryOps opcode = binOp->getOpcode();
66  if (opcode == Instruction::SDiv || opcode == Instruction::UDiv ||
67  opcode == Instruction::SRem || opcode == Instruction::URem) {
68 
69  CastInst *denominator =
70  CastInst::CreateIntegerCast(i->getOperand(1),
71  Type::getInt64Ty(getGlobalContext()),
72  false, /* sign doesn't matter */
73  "int_cast_to_i64",
74  i);
75 
76  // Lazily bind the function to avoid always importing it.
77  if (!divZeroCheckFunction) {
78  Constant *fc = M.getOrInsertFunction("klee_div_zero_check",
79  Type::getVoidTy(getGlobalContext()),
80  Type::getInt64Ty(getGlobalContext()),
81  NULL);
82  divZeroCheckFunction = cast<Function>(fc);
83  }
84 
85  CallInst * ci = CallInst::Create(divZeroCheckFunction, denominator, "", &*i);
86 
87  // Set debug location of checking call to that of the div/rem
88  // operation so error locations are reported in the correct
89  // location.
90  ci->setDebugLoc(binOp->getDebugLoc());
91  moduleChanged = true;
92  }
93  }
94  }
95  }
96  }
97  return moduleChanged;
98 }
99 
100 char OvershiftCheckPass::ID;
101 
102 bool OvershiftCheckPass::runOnModule(Module &M) {
103  Function *overshiftCheckFunction = 0;
104 
105  bool moduleChanged = false;
106 
107  for (Module::iterator f = M.begin(), fe = M.end(); f != fe; ++f) {
108  for (Function::iterator b = f->begin(), be = f->end(); b != be; ++b) {
109  for (BasicBlock::iterator i = b->begin(), ie = b->end(); i != ie; ++i) {
110  if (BinaryOperator* binOp = dyn_cast<BinaryOperator>(i)) {
111  // find all shift instructions
112  Instruction::BinaryOps opcode = binOp->getOpcode();
113 
114  if (opcode == Instruction::Shl ||
115  opcode == Instruction::LShr ||
116  opcode == Instruction::AShr ) {
117  std::vector<llvm::Value*> args;
118 
119  // Determine bit width of first operand
120  uint64_t bitWidth=i->getOperand(0)->getType()->getScalarSizeInBits();
121 
122  ConstantInt *bitWidthC = ConstantInt::get(Type::getInt64Ty(getGlobalContext()),bitWidth,false);
123  args.push_back(bitWidthC);
124 
125  CastInst *shift =
126  CastInst::CreateIntegerCast(i->getOperand(1),
127  Type::getInt64Ty(getGlobalContext()),
128  false, /* sign doesn't matter */
129  "int_cast_to_i64",
130  i);
131  args.push_back(shift);
132 
133 
134  // Lazily bind the function to avoid always importing it.
135  if (!overshiftCheckFunction) {
136  Constant *fc = M.getOrInsertFunction("klee_overshift_check",
137  Type::getVoidTy(getGlobalContext()),
138  Type::getInt64Ty(getGlobalContext()),
139  Type::getInt64Ty(getGlobalContext()),
140  NULL);
141  overshiftCheckFunction = cast<Function>(fc);
142  }
143 
144  // Inject CallInstr to check if overshifting possible
145  CallInst* ci =
146 #if LLVM_VERSION_CODE >= LLVM_VERSION(3, 0)
147  CallInst::Create(overshiftCheckFunction, args, "", &*i);
148 #else
149  CallInst::Create(overshiftCheckFunction, args.begin(), args.end(), "", &*i);
150 #endif
151  // set debug information from binary operand to preserve it
152  ci->setDebugLoc(binOp->getDebugLoc());
153  moduleChanged = true;
154  }
155  }
156  }
157  }
158  }
159  return moduleChanged;
160 }