//===- 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 "SCUtils.h"
#include "safecode/ArrayBoundsCheck.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 on Structures 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: getDSNodeHandle()
//
// Description:
//  This method looks up the DSNodeHandle for a given LLVM value.  The context
//  of the value is the specified function, although if it is a global value,
//  the DSNodeHandle may exist within the global DSGraph.
//
// Return value:
//  A DSNodeHandle for the value is returned.  This DSNodeHandle could either
//  be in the function's DSGraph or from the GlobalsGraph.  Note that the
//  DSNodeHandle may represent a NULL DSNode.
//
DSNodeHandle
ArrayBoundsCheckStruct::getDSNodeHandle (const Value * V, const Function * F) {
  //
  // Get access to the points-to results.
  //
  EQTDDataStructures & dsaPass = getAnalysis<EQTDDataStructures>();

  //
  // Ensure that the function has a DSGraph
  //
  assert (dsaPass.hasDSGraph(*F) && "No DSGraph for function!\n");

  //
  // Lookup the DSNode for the value in the function's DSGraph.
  //
  DSGraph * TDG = dsaPass.getDSGraph(*F);
  DSNodeHandle DSH = TDG->getNodeForValue(V);

  //
  // If the value wasn't found in the function's DSGraph, then maybe we can
  // find the value in the globals graph.
  //
  if ((DSH.isNull()) && (isa<GlobalValue>(V))) {
    //
    // Try looking up this DSNode value in the globals graph.  Note that
    // globals are put into equivalence classes; we may need to first find the
    // equivalence class to which our global belongs, find the global that
    // represents all globals in that equivalence class, and then look up the
    // DSNode Handle for *that* global.
    //
    DSGraph * GlobalsGraph = TDG->getGlobalsGraph ();
    DSH = GlobalsGraph->getNodeForValue(V);
    if (DSH.isNull()) {
      //
      // DSA does not currently handle global aliases.
      //
      if (!isa<GlobalAlias>(V)) {
        //
        // We have to dig into the globalEC of the DSGraph to find the DSNode.
        //
        const GlobalValue * GV = dyn_cast<GlobalValue>(V);
        const GlobalValue * Leader;
        Leader = GlobalsGraph->getGlobalECs().getLeaderValue(GV);
        DSH = GlobalsGraph->getNodeForValue(Leader);
      }
    }
  }

  return DSH;
}

//
// 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>();

  //
  // 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();
  DSNode * N = getDSNodeHandle (PointerOperand, F).getNode();
  if (N) {
    //
    // If DSA says that the object is type-known but not an array node, then
    // we know that this is just structure indexing.  We can therefore declare
    // it safe.
    //
    if ((!N->isNodeCompletelyFolded()) &&
        (!(N->isArrayNode())) &&
        (!(N->isIncompleteNode())) &&
        (!(N->isUnknownNode())) &&
        (!(N->isIntToPtrNode())) &&
        (!(N->isExternalNode()))) {
      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