| //===- 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 "ArrayBoundsCheck.h" |
| #include "safecode/SAFECodeConfig.h" |
| #include "safecode/Support/AllocatorInfo.h" |
| |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
| |
| using namespace llvm; |
| |
| |
| namespace { |
| STATISTIC (allGEPs , "Total Number of GEPs Queried"); |
| STATISTIC (safeGEPs , "Number of GEPs Proven Safe Statically"); |
| } |
| |
| NAMESPACE_SC_BEGIN |
| |
| namespace { |
| RegisterPass<ArrayBoundsCheckLocal> X ("abc-local", "Local Array Bounds Check pass"); |
| RegisterAnalysisGroup<ArrayBoundsCheckGroup> ABCGroup(X); |
| } |
| |
| char ArrayBoundsCheckLocal::ID = 0; |
| |
| bool |
| ArrayBoundsCheckLocal::runOnFunction(Function & F) { |
| intrinsicPass = &getAnalysis<InsertSCIntrinsic>(); |
| abcPass = &getAnalysis<ArrayBoundsCheckGroup>(); |
| TD = &getAnalysis<TargetData>(); |
| SE = &getAnalysis<ScalarEvolution>(); |
| return false; |
| } |
| |
| // |
| // Function: isGEPSafe() |
| // |
| // Description: |
| // Determine whether the GEP will always generate a pointer that lands within |
| // the bounds of the object. |
| // |
| // Inputs: |
| // TD - The TargetData pass which should be used for finding type-sizes and |
| // offsets of elements within a derived type. |
| // 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) { |
| // |
| // Update the count of GEPs queried. |
| // |
| ++allGEPs; |
| |
| Value * PointerOperand = GEP->getPointerOperand(); |
| |
| Value * objSize = intrinsicPass->getObjectSize(PointerOperand); |
| if (!objSize) |
| return false; |
| |
| // |
| // Calculate the: |
| // offset: Distance from base pointer to 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 * GEPBase = SE->getSCEV(PointerOperand); |
| const SCEV * offset = SE->getMinusSCEV(SE->getSCEV(GEP), GEPBase); |
| const SCEV * zero = SE->getSCEV(Constant::getNullValue(TD->getIntPtrType(getGlobalContext()))); |
| |
| // |
| // 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) { |
| return false; |
| } |
| |
| // |
| // 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) { |
| ++safeGEPs; |
| return true; |
| } |
| |
| // |
| // We cannot statically prove that the GEP is safe. Ask another array bounds |
| // checking pass to prove the GEP safe. |
| // |
| return abcPass->isGEPSafe(GEP); |
| } |
| |
| |
| NAMESPACE_SC_END |