path: root/lib/Analysis/DataStructure/Local.cpp

//===- Local.cpp - Compute a local data structure graph for a function ----===//
// 
//                     The LLVM Compiler Infrastructure
//
// 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.
// 
//===----------------------------------------------------------------------===//
//
// Compute the local version of the data structure graph for a function.  The
// external interface to this file is the DSGraph constructor.
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/DataStructure/DataStructure.h"
#include "llvm/Analysis/DataStructure/DSGraph.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Instructions.h"
#include "llvm/Intrinsics.h"
#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Target/TargetData.h"
#include "Support/CommandLine.h"
#include "Support/Debug.h"
#include "Support/Timer.h"

// FIXME: This should eventually be a FunctionPass that is automatically
// aggregated into a Pass.
//
#include "llvm/Module.h"

using namespace llvm;

static RegisterAnalysis<LocalDataStructures>
X("datastructure", "Local Data Structure Analysis");

static cl::opt<bool>
TrackIntegersAsPointers("dsa-track-integers", cl::Hidden,
         cl::desc("If this is set, track integers as potential pointers"));

namespace llvm {
namespace DS {
  // isPointerType - Return true if this type is big enough to hold a pointer.
  bool isPointerType(const Type *Ty) {
    if (isa<PointerType>(Ty))
      return true;
    else if (TrackIntegersAsPointers && Ty->isPrimitiveType() &&Ty->isInteger())
      return Ty->getPrimitiveSize() >= PointerSize;
    return false;
  }
}}

using namespace DS;

namespace {
  cl::opt<bool>
  DisableDirectCallOpt("disable-direct-call-dsopt", cl::Hidden,
                       cl::desc("Disable direct call optimization in "
                                "DSGraph construction"));
  cl::opt<bool>
  DisableFieldSensitivity("disable-ds-field-sensitivity", cl::Hidden,
                          cl::desc("Disable field sensitivity in DSGraphs"));

  //===--------------------------------------------------------------------===//
  //  GraphBuilder Class
  //===--------------------------------------------------------------------===//
  //
  /// This class is the builder class that constructs the local data structure
  /// graph by performing a single pass over the function in question.
  ///
  class GraphBuilder : InstVisitor<GraphBuilder> {
    DSGraph &G;
    DSNodeHandle *RetNode;               // Node that gets returned...
    DSScalarMap &ScalarMap;
    std::vector<DSCallSite> *FunctionCalls;

  public:
    GraphBuilder(Function &f, DSGraph &g, DSNodeHandle &retNode, 
                 std::vector<DSCallSite> &fc)
      : G(g), RetNode(&retNode), ScalarMap(G.getScalarMap()),
        FunctionCalls(&fc) {

      // Create scalar nodes for all pointer arguments...
      for (Function::aiterator I = f.abegin(), E = f.aend(); I != E; ++I)
        if (isPointerType(I->getType()))
          getValueDest(*I);

      visit(f);  // Single pass over the function
    }

    // GraphBuilder ctor for working on the globals graph
    GraphBuilder(DSGraph &g)
      : G(g), RetNode(0), ScalarMap(G.getScalarMap()), FunctionCalls(0) {
    }

    void mergeInGlobalInitializer(GlobalVariable *GV);

  private:
    // Visitor functions, used to handle each instruction type we encounter...
    friend class InstVisitor<GraphBuilder>;
    void visitMallocInst(MallocInst &MI) { handleAlloc(MI, true); }
    void visitAllocaInst(AllocaInst &AI) { handleAlloc(AI, false); }
    void handleAlloc(AllocationInst &AI, bool isHeap);

    void visitPHINode(PHINode &PN);

    void visitGetElementPtrInst(User &GEP);
    void visitReturnInst(ReturnInst &RI);
    void visitLoadInst(LoadInst &LI);
    void visitStoreInst(StoreInst &SI);
    void visitCallInst(CallInst &CI);
    void visitInvokeInst(InvokeInst &II);
    void visitSetCondInst(SetCondInst