//===- ArrayBoundCheckStruct.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.
// 
//===----------------------------------------------------------------------===//
//
// This file implements the ArrayBoundsCheckStruct pass.  This pass utilizes
// type-safety information from points-to analysis to prove whether GEPs are
// safe (they do not create a pointer outside of the memory object).  It is
// primarily designed to alleviate run-time checks on GEPs used for structure
// indexing (hence the clever name).
//
//===----------------------------------------------------------------------===//

#define DEBUG_TYPE "abc-struct"

#include "ArrayBoundsCheck.h"
#include "SCUtils.h"
#include "safecode/SAFECodeConfig.h"
#include "safecode/Support/AllocatorInfo.h"

#include "dsa/DSGraph.h"
#include "dsa/DSNode.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<ArrayBoundsCheckStruct>
  X ("abc-struct", "Structure Indexing Array Bounds Check pass");

  RegisterAnalysisGroup<ArrayBoundsCheckGroup> ABCGroup(X);
}

char ArrayBoundsCheckStruct::ID = 0;

//
// Method: runOnFunction()
//
// Description:
//  This is the entry point for this analysis pass.  We grab the required
//  analysis results from other passes here.  However, we don't actually
//  compute anything in this method.  Instead, we compute results when queried
//  by other passes.  This makes the bet that each GEP will only be quered
//  once, and only if some other analysis pass can't prove it safe before this
//  pass can.
//
// Inputs:
//  F - A reference to the function to analyze.
//
// Return value:
//  true  - This pass modified the function (which should never happen).
//  false - This pass did not modify the function.
//
bool
ArrayBoundsCheckStruct::runOnFunction(Function & F) {
  //
  // Get required analysis results from other passes.
  //
  abcPass = &getAnalysis<ArrayBoundsCheckGroup>();
  dsaPass = &getAnalysis<DSNodePass>();
  TD = &getAnalysis<TargetData>();

  //
  // We don't make any changes, so 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
ArrayBoundsCheckStruct::isGEPSafe (GetElementPtrInst * GEP) {
  //
  // Update the count of GEPs queried.
  //
  ++allGEPs;

  //
  // Get the source pointer of the GEP.  This is the pointer off of which the
  // indexing operation takes place.
  //
  Value * PointerOperand = GEP->getPointerOperand();

  //
  // Determine whether the pointer is for a type-known object.
  //
  Function * F = GEP->getParent()->getParent();
  if (DSNode *  DSN = dsaPass->getDSNode(PointerOperand, F)) {
    if (!(DSN->isNodeCompletelyFolded())) {
      //
      // The pointer points to a type-known object.  If the indices all index
      // into structures, then the GEP is safe.
      //
      if (indexesStructsOnly (GEP)) {
        ++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