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

//===- Local.cpp - Compute a local data structure graph for a function ----===//
//
// 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.h"
#include "llvm/Analysis/DSGraph.h"
#include "llvm/iMemory.h"
#include "llvm/iTerminators.h"
#include "llvm/iPHINode.h"
#include "llvm/iOther.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Function.h"
#include "llvm/GlobalVariable.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Target/TargetData.h"
#include "Support/Statistic.h"
#include "Support/Timer.h"
#include "Support/CommandLine.h"

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

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

namespace DS {
  // FIXME: Do something smarter with target data!
  TargetData TD("temp-td");

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

  //===--------------------------------------------------------------------===//
  //  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;
    std::vector<DSNode*> &Nodes;
    DSNodeHandle &RetNode;               // Node that gets returned...
    hash_map<Value*, DSNodeHandle> &ScalarMap;
    std::vector<DSCallSite> &FunctionCalls;

  public:
    GraphBuilder(DSGraph &g, std::vector<DSNode*> &nodes, DSNodeHandle &retNode,
                 hash_map<Value*, DSNodeHandle> &SM,
                 std::vector<DSCallSite> &fc)
      : G(g), Nodes(nodes), RetNode(retNode), ScalarMap(SM), FunctionCalls(fc) {

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

      visit(G.getFunction());  // Single pass over the function
    }

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

    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 visitSetCondInst(SetCondInst &SCI) {}  // SetEQ & friends are ignored
    void visitFreeInst(FreeInst &FI);
    void visitCastInst(CastInst &CI);
    void visitInstruction(Instruction &I);

  private:
    // Helper functions used to implement the visitation functions...

    /// createNode - Create a new DSNode, ensuring that it is properly added to
    /// the graph.
    ///
    DSNode *createNode(DSNode::NodeTy NodeType, const Type *Ty = 0) {
      DSNode *N = new DSNode(NodeType, Ty);   // Create the node
      Nodes.push_back(N);                     // Add node to nodes list
      return N;
    }

    /// setDestTo - Set the ScalarMap entry for the specified value to point to
    /// the specified destination.  If the Value already points to a node, make
    /// sure to merge the two destinations together.
    ///
    void setDestTo(Value &V, const DSNodeHandle &NH);

    /// getValueDest - Return the DSNode that the actual value points to. 
    ///
    DSNodeHandle getValueDest(Value &V);

    /// getLink - This method is used to return the specified link in the
    /// specified node if one exists.  If a link does not already exist (it's
    /// null), then we create a new node, link it, then return it.
    ///
    DSNodeHandle &getLink(const DSNodeHandle &Node, unsigned Link = 0);
  };
}

//===----------------------------------------------------------------------===//
// DSGraph constructor - Simply use the GraphBuilder to construct the local
// graph.
DSGraph::DSGraph(Function &F, DSGraph *GG) : Func(&F), GlobalsGraph(GG) {
  PrintAuxCalls = false;
  // Use the graph builder to construct the local version of the graph
  GraphBuilder B(*this, Nodes, RetNode, ScalarMap, FunctionCalls);
#ifndef NDEBUG
  Timer::addPeakMemoryMeasurement();
#endif
  markIncompleteNodes(DSGraph::MarkFormalArgs);

  // Remove any nodes made dead due to merging...
  removeDeadNodes(DSGraph::KeepUnreachableGlobals);
}


//===----------------------------------------------------------------------===//
// Helper method implementations...
//

/// getValueDest - Return the DSNode that the actual value points to.
///
DSNodeHandle GraphBuilder::getValueDest(Value &Val) {
  Value *V = &Val;
  if (V == Constant::getNullValue(V->getType()))
    return 0;  // Null doesn't point to anything, don't add to ScalarMap!

  DSNodeHandle &NH = ScalarMap[V];
  if (NH.getNode())
    return NH;     // Already have a node?  Just return it...

  // Otherwise we need to create a new node to point to.
  // Check first for constant expressions that must be traversed to
  // extract the actual value.
  if (Constant *C = dyn_cast<Constant>(V))
    if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C)) {
      return NH = getValueDest(*CPR->getValue());
    } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
      if (CE->getOpcode() == Instruction::Cast)
        return NH = getValueDest(*CE->getOperand(0));
      if (CE->getOpcode() == Instruction::GetElementPtr) {
        visitGetElementPtrInst(*CE);
        hash_map<Value*, DSNodeHandle>::iterator I = ScalarMap.find(CE);
        assert(I != ScalarMap.end() && "GEP didn't get processed right?");
        return NH = I->second;
      }

      // This returns a conservative unknown node for any unhandled ConstExpr
      return NH = createNode(DSNode::UnknownNode);
    } else if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(C)) {
      // Random constants are unknown mem
      return NH = createNode(DSNode::UnknownNode);
    } else {
      assert(0 && "Unknown constant type!");
    }

  // Otherwise we need to create a new node to point to...
  DSNode *N;
  if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) {
    // Create a new global node for this global variable...
    N = createNode(DSNode::GlobalNode, GV->getType()->getElementType());
    N->addGlobal(GV);
  } else {
    // Otherwise just create a shadow node
    N = createNode(DSNode::ShadowNode);
  }

  NH.setNode(N);      // Remember that we are pointing to it...
  NH.setOffset(0);
  return NH;
}


/// getLink - This method is used to return the specified link in the
/// specified node if one exists.  If a link does not already exist (it's
/// null), then we create a new node, link it, then return it.  We must
/// specify the type of the Node field we are accessing so that we know what
/// type should be linked to if we need to create a new node.
///
DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node, unsigned LinkNo) {
  DSNodeHandle &Node = const_cast<DSNodeHandle&>(node);
  DSNodeHandle &Link = Node.getLink(LinkNo);
  if (!Link.getNode()) {