| //===- ArrayBoundCheck.cpp - Static Array Bounds Checking --------------------// |
| // |
| // The SAFECode Compiler |
| // |
| // This file was developed by the LLVM research group and is distributed under |
| // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // ArrayBoundsCheckLocal - It tries to prove a GEP is safe only based on local |
| // information, that is, the size of global variables and the size of objects |
| // being allocated inside a function. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #define DEBUG_TYPE "abc-local" |
| |
| #include "safecode/ArrayBoundsCheck.h" |
| |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
| |
| #include <set> |
| #include <queue> |
| |
| using namespace llvm; |
| |
| namespace { |
| STATISTIC (allGEPs , "Total Number of GEPs Queried"); |
| STATISTIC (safeGEPs , "Number of GEPs Proven Safe Statically"); |
| STATISTIC (unsafeGEPs , "Number of GEPs Proven Unsafe Statically"); |
| } |
| |
| RegisterPass<ArrayBoundsCheckLocal> |
| X ("abc-local", "Local Array Bounds Check pass"); |
| |
| static RegisterAnalysisGroup<ArrayBoundsCheckGroup> |
| ABCGroup (X); |
| |
| char ArrayBoundsCheckLocal::ID = 0; |
| |
| // |
| // Function: findObject() |
| // |
| // Description: |
| // Find the singular memory object to which this pointer points (if such a |
| // singular object exists and is easy to find). |
| // |
| static Value * |
| findObject (Value * obj) { |
| std::set<Value *> exploredObjects; |
| std::set<Value *> objects; |
| std::queue<Value *> queue; |
| |
| queue.push(obj); |
| while (!queue.empty()) { |
| Value * o = queue.front(); |
| queue.pop(); |
| if (exploredObjects.count(o)) continue; |
| |
| exploredObjects.insert(o); |
| |
| if (isa<CastInst>(o)) { |
| queue.push(cast<CastInst>(o)->getOperand(0)); |
| } else if (isa<GetElementPtrInst>(o)) { |
| queue.push(cast<GetElementPtrInst>(o)->getPointerOperand()); |
| } else if (isa<PHINode>(o)) { |
| PHINode * p = cast<PHINode>(o); |
| for(unsigned int i = 0; i < p->getNumIncomingValues(); ++i) { |
| queue.push(p->getIncomingValue(i)); |
| } |
| } else { |
| objects.insert(o); |
| } |
| } |
| return objects.size() == 1 ? *(objects.begin()) : NULL; |
| } |
| |
| // |
| // Method: visitGetElementPtrInst() |
| // |
| // Description: |
| // This visitor method determines whether the specified GEP always stays |
| // within the bounds of an allocated object. |
| // |
| void |
| ArrayBoundsCheckLocal::visitGetElementPtrInst (GetElementPtrInst & GEP) { |
| // |
| // Get information about allocators. |
| // |
| AllocatorInfoPass & AIP = getAnalysis<AllocatorInfoPass>(); |
| |
| // |
| // Update the count of GEPs queried. |
| // |
| ++allGEPs; |
| |
| // |
| // Get the checked pointer and try to find the memory object from which it |
| // originates. If we can't find the memory object, let some other static |
| // array bounds checking pass have a crack at it. |
| // |
| Value * PointerOperand = GEP.getPointerOperand(); |
| Value * memObject = findObject (PointerOperand); |
| if (!memObject) |
| return; |
| Value * objSize = AIP.getObjectSize(memObject); |
| if (!objSize) |
| return; |
| |
| // |
| // Calculate the: |
| // offset: Distance from the start of the memory object to the calculated |
| // pointer |
| // zero : The zero value |
| // bounds: The size of the object |
| // diff : The difference between the bounds and the offset |
| // |
| // SCEVs for GEP indexing operations seems to be the size of a pointer. |
| // Therefore, use an integer size equal to the pointer size. |
| // |
| const SCEV * base = SE->getSCEV(memObject); |
| const SCEV * offset = SE->getMinusSCEV(SE->getSCEV(&GEP), base); |
| const SCEV * zero = SE->getSCEV(Constant::getNullValue(TD->getIntPtrType(GEP.getType()))); |
| |
| // |
| // Create an SCEV describing the bounds of the object. On 64-bit platforms, |
| // this may be a 32-bit integer while the offset value may be a 64-bit |
| // integer. In that case, we need to create a new SCEV that zero-extends |
| // the object size from 32 to 64 bits. |
| // |
| const SCEV * bounds = SE->getSCEV(objSize); |
| if ((TD->getTypeAllocSize (bounds->getType())) < |
| (TD->getTypeAllocSize (offset->getType()))) { |
| bounds = SE->getZeroExtendExpr(bounds, offset->getType()); |
| } |
| const SCEV * diff = SE->getMinusSCEV(bounds, offset); |
| |
| // |
| // If the offset is less than zero, then we know that we are indexing |
| // backwards from the beginning of the object. We know that this is illegal; |
| // declare it unsafe. |
| // |
| if ((SE->getSMaxExpr(offset, zero) == zero) && (offset != zero)) { |
| ++unsafeGEPs; |
| return; |
| } |
| |
| // |
| // Otherwise, we are indexing zero or more bytes forward. Determine whether |
| // we will index past the end of the object. |
| // |
| if ((SE->getSMaxExpr(diff, zero) == diff) && (diff != zero)) { |
| ++safeGEPs; |
| SafeGEPs.insert (&GEP); |
| return; |
| } |
| |
| // |
| // We cannot statically prove that the GEP is safe. |
| // |
| return; |
| } |
| |
| bool |
| ArrayBoundsCheckLocal::runOnFunction(Function & F) { |
| // |
| // Get required analysis passes. |
| // |
| TD = &getAnalysis<DataLayout>(); |
| SE = &getAnalysis<ScalarEvolution>(); |
| |
| // |
| // Look for all GEPs in the function and try to prove that they're safe. |
| // |
| visit (F); |
| |
| // |
| // We modify nothing; return false. |
| // |
| return false; |
| } |
| |
| // |
| // Function: isGEPSafe() |
| // |
| // Description: |
| // Determine whether the GEP will always generate a pointer that lands within |
| // the bounds of the object. |
| // |
| // Inputs: |
| // GEP - The getelementptr instruction to check. |
| // |
| // Return value: |
| // true - The GEP never generates a pointer outside the bounds of the object. |
| // false - The GEP may generate a pointer outside the bounds of the object. |
| // There may also be cases where we know that the GEP *will* return an |
| // out-of-bounds pointer; we let pointer rewriting take care of those |
| // cases. |
| // |
| bool |
| ArrayBoundsCheckLocal::isGEPSafe (GetElementPtrInst * GEP) { |
| return ((SafeGEPs.count(GEP)) > 0); |
| } |
| |