← Back to branch summary

~ubuntu-branches/ubuntu/saucy/clamav/saucy-backports

« back to all changes in this revision

Viewing changes to .pc/0004-Fix-FTBFS-with-LLVM-3.1-3.4.patch/libclamav/c++/ClamBCRTChecks.cpp

  • Committer: Package Import Robot
  • Author(s): Scott Kitterman
  • Date: 2014-07-15 01:08:10 UTC
  • mfrom: (0.35.47 sid)
  • Revision ID: package-import@ubuntu.com-20140715010810-ru66ek4fun2iseba
Tags: 0.98.4+dfsg-2~ubuntu13.10.1
https://launchpad.net/bugs/1341962
No-change backport to saucy (LP: #1341962)

Show diffs side-by-side

added added

removed removed

Lines of Context:
.pc/0004-Fix-FTBFS-with-LLVM-3.1-3.4.patch/libclamav/c++/ClamBCRTChecks.cpp
 
1
/*
 
2
 *  Compile LLVM bytecode to ClamAV bytecode.
 
3
 *
 
4
 *  Copyright (C) 2009-2013 Sourcefire, Inc.
 
5
 *
 
6
 *  Authors: Török Edvin
 
7
 *
 
8
 *  This program is free software; you can redistribute it and/or modify
 
9
 *  it under the terms of the GNU General Public License version 2 as
 
10
 *  published by the Free Software Foundation.
 
11
 *
 
12
 *  This program is distributed in the hope that it will be useful,
 
13
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
14
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
15
 *  GNU General Public License for more details.
 
16
 *
 
17
 *  You should have received a copy of the GNU General Public License
 
18
 *  along with this program; if not, write to the Free Software
 
19
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 
20
 *  MA 02110-1301, USA.
 
21
 */
 
22
#define DEBUG_TYPE "clambc-rtcheck"
 
23
#include "ClamBCModule.h"
 
24
#include "ClamBCDiagnostics.h"
 
25
#include "llvm/ADT/DenseSet.h"
 
26
#include "llvm/ADT/PostOrderIterator.h"
 
27
#include "llvm/ADT/SCCIterator.h"
 
28
#include "llvm/Analysis/CallGraph.h"
 
29
#include "llvm/Analysis/Verifier.h"
 
30
#include "llvm/Analysis/DebugInfo.h"
 
31
#include "llvm/Analysis/Dominators.h"
 
32
#include "llvm/Analysis/ConstantFolding.h"
 
33
//#include "llvm/Analysis/LiveValues.h"
 
34
//
 
35
#ifdef LLVM29
 
36
#include "llvm/Analysis/ValueTracking.h"
 
37
#include "PointerTracking.h"
 
38
#else
 
39
#include "llvm/Analysis/PointerTracking.h"
 
40
#endif
 
41
#include "llvm/Analysis/ScalarEvolution.h"
 
42
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
 
43
#include "llvm/Analysis/ScalarEvolutionExpander.h"
 
44
#include "llvm/Config/config.h"
 
45
#include "llvm/DerivedTypes.h"
 
46
#include "llvm/Instructions.h"
 
47
#include "llvm/IntrinsicInst.h"
 
48
#include "llvm/Intrinsics.h"
 
49
#include "llvm/LLVMContext.h"
 
50
#include "llvm/Module.h"
 
51
#include "llvm/Pass.h"
 
52
#include "llvm/Support/CommandLine.h"
 
53
#include "llvm/Support/DataFlow.h"
 
54
#include "llvm/Support/InstIterator.h"
 
55
#include "llvm/Support/InstVisitor.h"
 
56
#include "llvm/Support/GetElementPtrTypeIterator.h"
 
57
#include "llvm/ADT/DepthFirstIterator.h"
 
58
#include "llvm/Target/TargetData.h"
 
59
#include "llvm/Transforms/Scalar.h"
 
60
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
61
#include "llvm/Support/Debug.h"
 
62
#include "llvm30_compat.h"
 
63
 
 
64
#ifndef LLVM28
 
65
#define LLVM28
 
66
#endif
 
67
#ifdef LLVM28
 
68
#define DEFINEPASS(passname) passname() : FunctionPass(ID)
 
69
#else
 
70
#define DEFINEPASS(passname) passname() : FunctionPass(&ID)
 
71
#endif
 
72
 
 
73
using namespace llvm;
 
74
#ifndef LLVM29
 
75
static Value *GetUnderlyingObject(Value *P, TargetData *TD)
 
76
{
 
77
    return P->getUnderlyingObject();
 
78
}
 
79
#endif
 
80
namespace llvm {
 
81
    class PtrVerifier;
 
82
 
 
83
#ifdef LLVM30
 
84
  void initializePtrVerifierPass(PassRegistry&);
 
85
#endif
 
86
 
 
87
  class PtrVerifier : public FunctionPass {
 
88
  private:
 
89
    DenseSet<Function*> badFunctions;
 
90
    CallGraphNode *rootNode;
 
91
  public:
 
92
    static char ID;
 
93
    DEFINEPASS(PtrVerifier), rootNode(0), PT(), TD(), SE(), DT(),
 
94
    AbrtBB(), EP() {
 
95
#ifdef LLVM30
 
96
        initializePtrVerifierPass(*PassRegistry::getPassRegistry());
 
97
#endif
 
98
        Changed = false;
 
99
        valid = false;
 
100
    }
 
101
 
 
102
    virtual bool runOnFunction(Function &F) {
 
103
      DEBUG(errs() << "Running on " << F.getName() << "\n");
 
104
      DEBUG(F.dump());
 
105
      Changed = false;
 
106
      BaseMap.clear();
 
107
      BoundsMap.clear();
 
108
      AbrtBB = 0;
 
109
      valid = true;
 
110
 
 
111
      if (!rootNode) {
 
112
        rootNode = getAnalysis<CallGraph>().getRoot();
 
113
        // No recursive functions for now.
 
114
        // In the future we may insert runtime checks for stack depth.
 
115
        for (scc_iterator<CallGraphNode*> SCCI = scc_begin(rootNode),
 
116
             E = scc_end(rootNode); SCCI != E; ++SCCI) {
 
117
          const std::vector<CallGraphNode*> &nextSCC = *SCCI;
 
118
          if (nextSCC.size() > 1 || SCCI.hasLoop()) {
 
119
            errs() << "INVALID: Recursion detected, callgraph SCC components: ";
 
120
            for (std::vector<CallGraphNode*>::const_iterator I = nextSCC.begin(),
 
121
                 E = nextSCC.end(); I != E; ++I) {
 
122
              Function *FF = (*I)->getFunction();
 
123
              if (FF) {
 
124
                errs() << FF->getName() << ", ";
 
125
                badFunctions.insert(FF);
 
126
              }
 
127
            }
 
128
            if (SCCI.hasLoop())
 
129
              errs() << "(self-loop)";
 
130
            errs() << "\n";
 
131
          }
 
132
          // we could also have recursion via function pointers, but we don't
 
133
          // allow calls to unknown functions, see runOnFunction() below
 
134
        }
 
135
      }
 
136
 
 
137
      BasicBlock::iterator It = F.getEntryBlock().begin();
 
138
      while (isa<AllocaInst>(It) || isa<PHINode>(It)) ++It;
 
139
      EP = &*It;
 
140
 
 
141
      TD = &getAnalysis<TargetData>();
 
142
      SE = &getAnalysis<ScalarEvolution>();
 
143
      PT = &getAnalysis<PointerTracking>();
 
144
      DT = &getAnalysis<DominatorTree>();
 
145
 
 
146
      std::vector<Instruction*> insns;
 
147
 
 
148
      BasicBlock *LastBB = 0;
 
149
      bool skip = false;
 
150
      for (inst_iterator I=inst_begin(F),E=inst_end(F); I != E;++I) {
 
151
        Instruction *II = &*I;
 
152
        if (II->getParent() != LastBB) {
 
153
            LastBB = II->getParent();
 
154
            skip = DT->getNode(LastBB) == 0;
 
155
        }
 
156
        if (skip)
 
157
            continue;
 
158
        if (isa<LoadInst>(II) || isa<StoreInst>(II) || isa<MemIntrinsic>(II))
 
159
          insns.push_back(II);
 
160
        if (CallInst *CI = dyn_cast<CallInst>(II)) {
 
161
          Value *V = CI->getCalledValue()->stripPointerCasts();
 
162
          Function *F = dyn_cast<Function>(V);
 
163
          if (!F) {
 
164
            printLocation(CI, true);
 
165
            errs() << "Could not determine call target\n";
 
166
            valid = 0;
 
167
            continue;
 
168
          }
 
169
          if (!F->isDeclaration())
 
170
            continue;
 
171
          insns.push_back(CI);
 
172
        }
 
173
      }
 
174
      while (!insns.empty()) {
 
175
        Instruction *II = insns.back();
 
176
        insns.pop_back();
 
177
        DEBUG(dbgs() << "checking " << *II << "\n");
 
178
        if (LoadInst *LI = dyn_cast<LoadInst>(II)) {
 
179
          constType *Ty = LI->getType();
 
180
          valid &= validateAccess(LI->getPointerOperand(),
 
181
                                  TD->getTypeAllocSize(Ty), LI);
 
182
        } else if (StoreInst *SI = dyn_cast<StoreInst>(II)) {
 
183
          constType *Ty = SI->getOperand(0)->getType();
 
184
          valid &= validateAccess(SI->getPointerOperand(),
 
185
                                  TD->getTypeAllocSize(Ty), SI);
 
186
        } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(II)) {
 
187
          valid &= validateAccess(MI->getDest(), MI->getLength(), MI);
 
188
          if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) {
 
189
            valid &= validateAccess(MTI->getSource(), MI->getLength(), MI);
 
190
          }
 
191
        } else if (CallInst *CI = dyn_cast<CallInst>(II)) {
 
192
          Value *V = CI->getCalledValue()->stripPointerCasts();
 
193
          Function *F = cast<Function>(V);
 
194
          const FunctionType *FTy = F->getFunctionType();
 
195
          CallSite CS(CI);
 
196
 
 
197
          if (F->getName().equals("memcmp") && FTy->getNumParams() == 3) {
 
198
            valid &= validateAccess(CS.getArgument(0), CS.getArgument(2), CI);
 
199
            valid &= validateAccess(CS.getArgument(1), CS.getArgument(2), CI);
 
200
            continue;
 
201
          }
 
202
          unsigned i;
 
203
#ifdef CLAMBC_COMPILER
 
204
          i = 0;
 
205
#else
 
206
          i = 1;// skip hidden ctx*
 
207
#endif
 
208
          for (;i<FTy->getNumParams();i++) {
 
209
            if (isa<PointerType>(FTy->getParamType(i))) {
 
210
              Value *Ptr = CS.getArgument(i);
 
211
              if (i+1 >= FTy->getNumParams()) {
 
212
                printLocation(CI, false);
 
213
                errs() << "Call to external function with pointer parameter last cannot be analyzed\n";
 
214
                errs() << *CI << "\n";
 
215
                valid = 0;
 
216
                break;
 
217
              }
 
218
              Value *Size = CS.getArgument(i+1);
 
219
              if (!Size->getType()->isIntegerTy()) {
 
220
                printLocation(CI, false);
 
221
                errs() << "Pointer argument must be followed by integer argument representing its size\n";
 
222
                errs() << *CI << "\n";
 
223
                valid = 0;
 
224
                break;
 
225
              }
 
226
              valid &= validateAccess(Ptr, Size, CI);
 
227
            }
 
228
          }
 
229
        }
 
230
      }
 
231
      if (badFunctions.count(&F))
 
232
        valid = 0;
 
233
 
 
234
      if (!valid) {
 
235
        DEBUG(F.dump());
 
236
        ClamBCModule::stop("Verification found errors!", &F);
 
237
        // replace function with call to abort
 
238
        std::vector<constType*>args;
 
239
        FunctionType* abrtTy = FunctionType::get(
 
240
          Type::getVoidTy(F.getContext()),args,false);
 
241
        Constant *func_abort =
 
242
          F.getParent()->getOrInsertFunction("abort", abrtTy);
 
243
 
 
244
        BasicBlock *BB = &F.getEntryBlock();
 
245
        Instruction *I = &*BB->begin();
 
246
        Instruction *UI = new UnreachableInst(F.getContext(), I);
 
247
        CallInst *AbrtC = CallInst::Create(func_abort, "", UI);
 
248
        AbrtC->setCallingConv(CallingConv::C);
 
249
        AbrtC->setTailCall(true);
 
250
        AbrtC->setDoesNotReturn(true);
 
251
        AbrtC->setDoesNotThrow(true);
 
252
        // remove all instructions from entry
 
253
        BasicBlock::iterator BBI = I, BBE=BB->end();
 
254
        while (BBI != BBE) {
 
255
            if (!BBI->use_empty())
 
256
                BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
 
257
            BB->getInstList().erase(BBI++);
 
258
        }
 
259
      }
 
260
      return Changed;
 
261
    }
 
262
 
 
263
    virtual void releaseMemory() {
 
264
      badFunctions.clear();
 
265
    }
 
266
 
 
267
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 
268
      AU.addRequired<TargetData>();
 
269
      AU.addRequired<DominatorTree>();
 
270
      AU.addRequired<ScalarEvolution>();
 
271
      AU.addRequired<PointerTracking>();
 
272
      AU.addRequired<CallGraph>();
 
273
    }
 
274
 
 
275
    bool isValid() const { return valid; }
 
276
  private:
 
277
    PointerTracking *PT;
 
278
    TargetData *TD;
 
279
    ScalarEvolution *SE;
 
280
    DominatorTree *DT;
 
281
    DenseMap<Value*, Value*> BaseMap;
 
282
    DenseMap<Value*, Value*> BoundsMap;
 
283
    BasicBlock *AbrtBB;
 
284
    bool Changed;
 
285
    bool valid;
 
286
    Instruction *EP;
 
287
 
 
288
    Instruction *getInsertPoint(Value *V)
 
289
    {
 
290
      BasicBlock::iterator It =  EP;
 
291
      if (Instruction *I = dyn_cast<Instruction>(V)) {
 
292
        It = I;
 
293
        ++It;
 
294
      }
 
295
      return &*It;
 
296
    }
 
297
 
 
298
    Value *getPointerBase(Value *Ptr)
 
299
    {
 
300
      if (BaseMap.count(Ptr))
 
301
        return BaseMap[Ptr];
 
302
      Value *P = Ptr->stripPointerCasts();
 
303
      if (BaseMap.count(P)) {
 
304
        return BaseMap[Ptr] = BaseMap[P];
 
305
      }
 
306
      Value *P2 = GetUnderlyingObject(P, TD);
 
307
      if (P2 != P) {
 
308
        Value *V = getPointerBase(P2);
 
309
        return BaseMap[Ptr] = V;
 
310
      }
 
311
 
 
312
      constType *P8Ty =
 
313
        PointerType::getUnqual(Type::getInt8Ty(Ptr->getContext()));
 
314
      if (PHINode *PN = dyn_cast<PHINode>(Ptr)) {
 
315
        BasicBlock::iterator It = PN;
 
316
        ++It;
 
317
        PHINode *newPN = PHINode::Create(P8Ty, HINT(PN->getNumIncomingValues()) ".verif.base", &*It);
 
318
        Changed = true;
 
319
        BaseMap[Ptr] = newPN;
 
320
 
 
321
        for (unsigned i=0;i<PN->getNumIncomingValues();i++) {
 
322
          Value *Inc = PN->getIncomingValue(i);
 
323
          Value *V = getPointerBase(Inc);
 
324
          newPN->addIncoming(V, PN->getIncomingBlock(i));
 
325
        }
 
326
        return newPN;
 
327
      }
 
328
      if (SelectInst *SI = dyn_cast<SelectInst>(Ptr)) {
 
329
        BasicBlock::iterator It = SI;
 
330
        ++It;
 
331
        Value *TrueB = getPointerBase(SI->getTrueValue());
 
332
        Value *FalseB = getPointerBase(SI->getFalseValue());
 
333
        if (TrueB && FalseB) {
 
334
          SelectInst *NewSI = SelectInst::Create(SI->getCondition(), TrueB,
 
335
                                                 FalseB, ".select.base", &*It);
 
336
          Changed = true;
 
337
          return BaseMap[Ptr] = NewSI;
 
338
        }
 
339
      }
 
340
      if (Ptr->getType() != P8Ty) {
 
341
        if (Constant *C = dyn_cast<Constant>(Ptr))
 
342
          Ptr = ConstantExpr::getPointerCast(C, P8Ty);
 
343
        else {
 
344
          Instruction *I = getInsertPoint(Ptr);
 
345
          Ptr = new BitCastInst(Ptr, P8Ty, "", I);
 
346
        }
 
347
      }
 
348
      return BaseMap[Ptr] = Ptr;
 
349
    }
 
350
 
 
351
    Value* getPointerBounds(Value *Base) {
 
352
      if (BoundsMap.count(Base))
 
353
        return BoundsMap[Base];
 
354
      constType *I64Ty =
 
355
        Type::getInt64Ty(Base->getContext());
 
356
#ifndef CLAMBC_COMPILER
 
357
      // first arg is hidden ctx
 
358
      if (Argument *A = dyn_cast<Argument>(Base)) {
 
359
          if (A->getArgNo() == 0) {
 
360
              constType *Ty = cast<PointerType>(A->getType())->getElementType();
 
361
              return ConstantInt::get(I64Ty, TD->getTypeAllocSize(Ty));
 
362
          }
 
363
      }
 
364
      if (LoadInst *LI = dyn_cast<LoadInst>(Base)) {
 
365
          Value *V = GetUnderlyingObject(LI->getPointerOperand()->stripPointerCasts(), TD);
 
366
          if (Argument *A = dyn_cast<Argument>(V)) {
 
367
              if (A->getArgNo() == 0) {
 
368
                  // pointers from hidden ctx are trusted to be at least the
 
369
                  // size they say they are
 
370
                  constType *Ty = cast<PointerType>(LI->getType())->getElementType();
 
371
                  return ConstantInt::get(I64Ty, TD->getTypeAllocSize(Ty));
 
372
              }
 
373
          }
 
374
      }
 
375
#endif
 
376
      if (PHINode *PN = dyn_cast<PHINode>(Base)) {
 
377
        BasicBlock::iterator It = PN;
 
378
        ++It;
 
379
        PHINode *newPN = PHINode::Create(I64Ty, HINT(PN->getNumIncomingValues()) ".verif.bounds", &*It);
 
380
        Changed = true;
 
381
        BoundsMap[Base] = newPN;
 
382
 
 
383
        bool good = true;
 
384
        for (unsigned i=0;i<PN->getNumIncomingValues();i++) {
 
385
          Value *Inc = PN->getIncomingValue(i);
 
386
          Value *B = getPointerBounds(Inc);
 
387
          if (!B) {
 
388
            good = false;
 
389
            B = ConstantInt::get(newPN->getType(), 0);
 
390
            DEBUG(dbgs() << "bounds not found while solving phi node: " << *Inc
 
391
                  << "\n");
 
392
          }
 
393
          newPN->addIncoming(B, PN->getIncomingBlock(i));
 
394
        }
 
395
        if (!good)
 
396
          newPN = 0;
 
397
        return BoundsMap[Base] = newPN;
 
398
      }
 
399
      if (SelectInst *SI = dyn_cast<SelectInst>(Base)) {
 
400
        BasicBlock::iterator It = SI;
 
401
        ++It;
 
402
        Value *TrueB = getPointerBounds(SI->getTrueValue());
 
403
        Value *FalseB = getPointerBounds(SI->getFalseValue());
 
404
        if (TrueB && FalseB) {
 
405
          SelectInst *NewSI = SelectInst::Create(SI->getCondition(), TrueB,
 
406
                                                 FalseB, ".select.bounds", &*It);
 
407
          Changed = true;
 
408
          return BoundsMap[Base] = NewSI;
 
409
        }
 
410
      }
 
411
 
 
412
      constType *Ty;
 
413
      Value *V = PT->computeAllocationCountValue(Base, Ty);
 
414
      if (!V) {
 
415
          Base = Base->stripPointerCasts();
 
416
          if (CallInst *CI = dyn_cast<CallInst>(Base)) {
 
417
              Function *F = CI->getCalledFunction();
 
418
              const FunctionType *FTy = F->getFunctionType();
 
419
              // last operand is always size for this API call kind
 
420
              if (F->isDeclaration() && FTy->getNumParams() > 0) {
 
421
                CallSite CS(CI);
 
422
                if (FTy->getParamType(FTy->getNumParams()-1)->isIntegerTy())
 
423
                  V = CS.getArgument(FTy->getNumParams()-1);
 
424
              }
 
425
          }
 
426
          if (!V)
 
427
              return BoundsMap[Base] = 0;
 
428
      } else {
 
429
        unsigned size = TD->getTypeAllocSize(Ty);
 
430
        if (size > 1) {
 
431
          Constant *C = cast<Constant>(V);
 
432
          C = ConstantExpr::getMul(C,
 
433
                                   ConstantInt::get(Type::getInt32Ty(C->getContext()),
 
434
                                                    size));
 
435
          V = C;
 
436
        }
 
437
      }
 
438
      if (V->getType() != I64Ty) {
 
439
        if (Constant *C = dyn_cast<Constant>(V))
 
440
          V = ConstantExpr::getZExt(C, I64Ty);
 
441
        else {
 
442
          Instruction *I = getInsertPoint(V);
 
443
          V = new ZExtInst(V, I64Ty, "", I);
 
444
        }
 
445
      }
 
446
      return BoundsMap[Base] = V;
 
447
    }
 
448
 
 
449
    MDNode *getLocation(Instruction *I, bool &Approximate, unsigned MDDbgKind)
 
450
    {
 
451
      Approximate = false;
 
452
      if (MDNode *Dbg = I->getMetadata(MDDbgKind))
 
453
        return Dbg;
 
454
      if (!MDDbgKind)
 
455
        return 0;
 
456
      Approximate = true;
 
457
      BasicBlock::iterator It = I;
 
458
      while (It != I->getParent()->begin()) {
 
459
        --It;
 
460
        if (MDNode *Dbg = It->getMetadata(MDDbgKind))
 
461
          return Dbg;
 
462
      }
 
463
      BasicBlock *BB = I->getParent();
 
464
      while ((BB = BB->getUniquePredecessor())) {
 
465
        It = BB->end();
 
466
        while (It != BB->begin()) {
 
467
          --It;
 
468
          if (MDNode *Dbg = It->getMetadata(MDDbgKind))
 
469
            return Dbg;
 
470
        }
 
471
      }
 
472
      return 0;
 
473
    }
 
474
 
 
475
    bool insertCheck(const SCEV *Idx, const SCEV *Limit, Instruction *I,
 
476
                     bool strict)
 
477
    {
 
478
      if (isa<SCEVCouldNotCompute>(Idx) && isa<SCEVCouldNotCompute>(Limit)) {
 
479
        errs() << "Could not compute the index and the limit!: \n" << *I << "\n";
 
480
        return false;
 
481
      }
 
482
      if (isa<SCEVCouldNotCompute>(Idx)) {
 
483
        errs() << "Could not compute index: \n" << *I << "\n";
 
484
        return false;
 
485
      }
 
486
      if (isa<SCEVCouldNotCompute>(Limit)) {
 
487
        errs() << "Could not compute limit: " << *I << "\n";
 
488
        return false;
 
489
      }
 
490
      BasicBlock *BB = I->getParent();
 
491
      BasicBlock::iterator It = I;
 
492
      BasicBlock *newBB = SplitBlock(BB, &*It, this);
 
493
      PHINode *PN;
 
494
      unsigned MDDbgKind = I->getContext().getMDKindID("dbg");
 
495
      //verifyFunction(*BB->getParent());
 
496
      if (!AbrtBB) {
 
497
        std::vector<constType*>args;
 
498
        FunctionType* abrtTy = FunctionType::get(
 
499
          Type::getVoidTy(BB->getContext()),args,false);
 
500
        args.push_back(Type::getInt32Ty(BB->getContext()));
 
501
        FunctionType* rterrTy = FunctionType::get(
 
502
          Type::getInt32Ty(BB->getContext()),args,false);
 
503
        Constant *func_abort =
 
504
          BB->getParent()->getParent()->getOrInsertFunction("abort", abrtTy);
 
505
        Constant *func_rterr =
 
506
          BB->getParent()->getParent()->getOrInsertFunction("bytecode_rt_error", rterrTy);
 
507
        AbrtBB = BasicBlock::Create(BB->getContext(), "", BB->getParent());
 
508
        PN = PHINode::Create(Type::getInt32Ty(BB->getContext()),HINT(1) "",
 
509
                                      AbrtBB);
 
510
        if (MDDbgKind) {
 
511
          CallInst *RtErrCall = CallInst::Create(func_rterr, PN, "", AbrtBB);
 
512
          RtErrCall->setCallingConv(CallingConv::C);
 
513
          RtErrCall->setTailCall(true);
 
514
          RtErrCall->setDoesNotThrow(true);
 
515
        }
 
516
        CallInst* AbrtC = CallInst::Create(func_abort, "", AbrtBB);
 
517
        AbrtC->setCallingConv(CallingConv::C);
 
518
        AbrtC->setTailCall(true);
 
519
        AbrtC->setDoesNotReturn(true);
 
520
        AbrtC->setDoesNotThrow(true);
 
521
        new UnreachableInst(BB->getContext(), AbrtBB);
 
522
        DT->addNewBlock(AbrtBB, BB);
 
523
        //verifyFunction(*BB->getParent());
 
524
      } else {
 
525
        PN = cast<PHINode>(AbrtBB->begin());
 
526
      }
 
527
      unsigned locationid = 0;
 
528
      bool Approximate;
 
529
      if (MDNode *Dbg = getLocation(I, Approximate, MDDbgKind)) {
 
530
        DILocation Loc(Dbg);
 
531
        locationid = Loc.getLineNumber() << 8;
 
532
        unsigned col = Loc.getColumnNumber();
 
533
        if (col > 254)
 
534
          col = 254;
 
535
        if (Approximate)
 
536
          col = 255;
 
537
        locationid |= col;
 
538
//      Loc.getFilename();
 
539
      } else {
 
540
        static int wcounters = 100000;
 
541
        locationid = (wcounters++)<<8;
 
542
        /*errs() << "fake location: " << (locationid>>8) << "\n";
 
543
        I->dump();
 
544
        I->getParent()->dump();*/
 
545
      }
 
546
      PN->addIncoming(ConstantInt::get(Type::getInt32Ty(BB->getContext()),
 
547
                                       locationid), BB);
 
548
 
 
549
      TerminatorInst *TI = BB->getTerminator();
 
550
      SCEVExpander expander(*SE OPT("SCEVexpander"));
 
551
      Value *IdxV = expander.expandCodeFor(Idx, Limit->getType(), TI);
 
552
/*      if (isa<PointerType>(IdxV->getType())) {
 
553
        IdxV = new PtrToIntInst(IdxV, Idx->getType(), "", TI);
 
554
      }*/
 
555
      //verifyFunction(*BB->getParent());
 
556
      Value *LimitV = expander.expandCodeFor(Limit, Limit->getType(), TI);
 
557
      //verifyFunction(*BB->getParent());
 
558
      Value *Cond = new ICmpInst(TI, strict ?
 
559
                                 ICmpInst::ICMP_ULT :
 
560
                                 ICmpInst::ICMP_ULE, IdxV, LimitV);
 
561
      //verifyFunction(*BB->getParent());
 
562
      BranchInst::Create(newBB, AbrtBB, Cond, TI);
 
563
      TI->eraseFromParent();
 
564
      // Update dominator info
 
565
      BasicBlock *DomBB =
 
566
        DT->findNearestCommonDominator(BB,
 
567
                                       DT->getNode(AbrtBB)->getIDom()->getBlock());
 
568
      DT->changeImmediateDominator(AbrtBB, DomBB);
 
569
      //verifyFunction(*BB->getParent());
 
570
      return true;
 
571
    }
 
572
   
 
573
    static void MakeCompatible(ScalarEvolution *SE, const SCEV*& LHS, const SCEV*& RHS) 
 
574
    {
 
575
      if (const SCEVZeroExtendExpr *ZL = dyn_cast<SCEVZeroExtendExpr>(LHS))
 
576
        LHS = ZL->getOperand();
 
577
      if (const SCEVZeroExtendExpr *ZR = dyn_cast<SCEVZeroExtendExpr>(RHS))
 
578
        RHS = ZR->getOperand();
 
579
 
 
580
      constType* LTy = SE->getEffectiveSCEVType(LHS->getType());
 
581
      constType *RTy = SE->getEffectiveSCEVType(RHS->getType());
 
582
      if (SE->getTypeSizeInBits(RTy) > SE->getTypeSizeInBits(LTy))
 
583
        LTy = RTy;
 
584
      LHS = SE->getNoopOrZeroExtend(LHS, LTy);
 
585
      RHS = SE->getNoopOrZeroExtend(RHS, LTy);
 
586
    }
 
587
    bool checkCond(Instruction *ICI, Instruction *I, bool equal)
 
588
    {
 
589
      for (Value::use_iterator JU=ICI->use_begin(),JUE=ICI->use_end();
 
590
           JU != JUE; ++JU) {
 
591
        Value *JU_V = *JU;
 
592
        if (BranchInst *BI = dyn_cast<BranchInst>(JU_V)) {
 
593
          if (!BI->isConditional())
 
594
            continue;
 
595
          BasicBlock *S = BI->getSuccessor(equal);
 
596
          if (DT->dominates(S, I->getParent()))
 
597
            return true;
 
598
        }
 
599
        if (BinaryOperator *BI = dyn_cast<BinaryOperator>(JU_V)) {
 
600
          if (BI->getOpcode() == Instruction::Or &&
 
601
              checkCond(BI, I, equal))
 
602
            return true;
 
603
          if (BI->getOpcode() == Instruction::And &&
 
604
              checkCond(BI, I, !equal))
 
605
            return true;
 
606
        }
 
607
      }
 
608
      return false;
 
609
    }
 
610
 
 
611
    bool checkCondition(Instruction *CI, Instruction *I)
 
612
    {
 
613
      for (Value::use_iterator U=CI->use_begin(),UE=CI->use_end();
 
614
           U != UE; ++U) {
 
615
        Value *U_V = *U;
 
616
        if (ICmpInst *ICI = dyn_cast<ICmpInst>(U_V)) {
 
617
          if (ICI->getOperand(0)->stripPointerCasts() == CI &&
 
618
              isa<ConstantPointerNull>(ICI->getOperand(1))) {
 
619
            if (checkCond(ICI, I, ICI->getPredicate() == ICmpInst::ICMP_EQ))
 
620
              return true;
 
621
          }
 
622
        }
 
623
      }
 
624
      return false;
 
625
    }
 
626
 
 
627
    bool validateAccess(Value *Pointer, Value *Length, Instruction *I)
 
628
    {
 
629
        // get base
 
630
        Value *Base = getPointerBase(Pointer);
 
631
 
 
632
        Value *SBase = Base->stripPointerCasts();
 
633
        // get bounds
 
634
        Value *Bounds = getPointerBounds(SBase);
 
635
        if (!Bounds) {
 
636
          printLocation(I, true);
 
637
          errs() << "no bounds for base ";
 
638
          printValue(SBase);
 
639
          errs() << " while checking access to ";
 
640
          printValue(Pointer);
 
641
          errs() << " of length ";
 
642
          printValue(Length);
 
643
          errs() << "\n";
 
644
 
 
645
          return false;
 
646
        }
 
647
 
 
648
        if (CallInst *CI = dyn_cast<CallInst>(Base->stripPointerCasts())) {
 
649
          if (I->getParent() == CI->getParent()) {
 
650
            printLocation(I, true);
 
651
            errs() << "no null pointer check of pointer ";
 
652
            printValue(Base, false, true);
 
653
            errs() << " obtained by function call";
 
654
            errs() << " before use in same block\n";
 
655
            return false;
 
656
          }
 
657
          if (!checkCondition(CI, I)) {
 
658
            printLocation(I, true);
 
659
            errs() << "no null pointer check of pointer ";
 
660
            printValue(Base, false, true);
 
661
            errs() << " obtained by function call";
 
662
            errs() << " before use\n";
 
663
            return false;
 
664
          }
 
665
        }
 
666
 
 
667
        constType *I64Ty =
 
668
          Type::getInt64Ty(Base->getContext());
 
669
        const SCEV *SLen = SE->getSCEV(Length);
 
670
        const SCEV *OffsetP = SE->getMinusSCEV(SE->getSCEV(Pointer),
 
671
                                               SE->getSCEV(Base));
 
672
        SLen = SE->getNoopOrZeroExtend(SLen, I64Ty);
 
673
        OffsetP = SE->getNoopOrZeroExtend(OffsetP, I64Ty);
 
674
        const SCEV *Limit = SE->getSCEV(Bounds);
 
675
        Limit = SE->getNoopOrZeroExtend(Limit, I64Ty);
 
676
 
 
677
        DEBUG(dbgs() << "Checking access to " << *Pointer << " of length " <<
 
678
              *Length << "\n");
 
679
        if (OffsetP == Limit) {
 
680
          printLocation(I, true);
 
681
          errs() << "OffsetP == Limit: " << *OffsetP << "\n";
 
682
          errs() << " while checking access to ";
 
683
          printValue(Pointer);
 
684
          errs() << " of length ";
 
685
          printValue(Length);
 
686
          errs() << "\n";
 
687
          return false;
 
688
        }
 
689
 
 
690
        if (SLen == Limit) {
 
691
          if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(OffsetP)) {
 
692
            if (SC->isZero())
 
693
              return true;
 
694
          }
 
695
          errs() << "SLen == Limit: " << *SLen << "\n";
 
696
          errs() << " while checking access to " << *Pointer << " of length "
 
697
            << *Length << " at " << *I << "\n";
 
698
          return false;
 
699
        }
 
700
 
 
701
        bool valid = true;
 
702
        SLen = SE->getAddExpr(OffsetP, SLen);
 
703
        // check that offset + slen <= limit; 
 
704
        // umax(offset+slen, limit) == limit is a sufficient (but not necessary
 
705
        // condition)
 
706
        const SCEV *MaxL = SE->getUMaxExpr(SLen, Limit);
 
707
        if (MaxL != Limit) {
 
708
          DEBUG(dbgs() << "MaxL != Limit: " << *MaxL << ", " << *Limit << "\n");
 
709
          valid &= insertCheck(SLen, Limit, I, false);
 
710
        }
 
711
 
 
712
        //TODO: nullpointer check
 
713
        const SCEV *Max = SE->getUMaxExpr(OffsetP, Limit);
 
714
        if (Max == Limit)
 
715
          return valid;
 
716
        DEBUG(dbgs() << "Max != Limit: " << *Max << ", " << *Limit << "\n");
 
717
 
 
718
        // check that offset < limit
 
719
        valid &= insertCheck(OffsetP, Limit, I, true);
 
720
        return valid;
 
721
    }
 
722
 
 
723
    bool validateAccess(Value *Pointer, unsigned size, Instruction *I)
 
724
    {
 
725
      return validateAccess(Pointer,
 
726
                            ConstantInt::get(Type::getInt32Ty(Pointer->getContext()),
 
727
                                             size), I);
 
728
    }
 
729
  };
 
730
  char PtrVerifier::ID;
 
731
 
 
732
}
 
733
#ifdef LLVM30
 
734
INITIALIZE_PASS_BEGIN(PtrVerifier, "", "", false, false)
 
735
INITIALIZE_PASS_DEPENDENCY(TargetData)
 
736
INITIALIZE_PASS_DEPENDENCY(DominatorTree)
 
737
INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
 
738
INITIALIZE_AG_DEPENDENCY(CallGraph)
 
739
INITIALIZE_PASS_DEPENDENCY(PointerTracking)
 
740
INITIALIZE_PASS_END(PtrVerifier, "clambcrtchecks", "ClamBC RTchecks", false, false)
 
741
#endif
 
742
 
 
743
 
 
744
llvm::Pass *createClamBCRTChecks()
 
745
{
 
746
  return new PtrVerifier();
 
747
}
 
748