<commit_before>{-# LANGUAGE ViewPatterns, BangPatterns, FlexibleInstances, MultiParamTypeClasses #-}
-- | This module implements the compositional pointer/escape analysis
-- described by <NAME> Rinard (http://doi.acm.org/10.1145/320384.320400).
--
-- This version is adapted to the LLVM IR (originally for Java).
--
-- Each program variable has a VariableNode to enable lookups easily
-- during the analysis (the ID in the graph is the ID of the LLVM IR
-- object).  Each VariableNode has a corresponding location that it
-- represents (either an internal node or an external node).  The
-- types of each node correspond to those in the bitcode.  The
-- location node for a VariableNode has an ID that is the negated ID
-- of the corresponding name.
--
-- Memoize the representative field GEP for each operation by caching
-- the deduced value in the EscapeGraph structure.
--
-- Add a sequence number to the EscapeGraph and increment it whenever
-- edges are added or removed.  This should make graph equality tests
-- much faster.
module Data.LLVM.Analysis.Escape (
  -- * Types
  EscapeResult,
  EscapeGraph(..),
  EscapeNode(..),
  EscapeEdge(..),
  PTEGraph,
  -- * Functions
  runEscapeAnalysis,
  escapeGraphAtLocation,
  localPointsTo,
  valueEscaped,
  valueProperlyEscaped,
  valueWillEscape,
  -- * Debugging
  viewEscapeGraph
  ) where

import Algebra.Lattice
import Data.Graph.Inductive hiding ( Gr )
import Data.GraphViz
import Data.List ( foldl', mapAccumR )
import Data.Map ( Map )
import qualified Data.Map as M
import Data.Set ( Set, (\\) )
import qualified Data.Set as S
import Data.Hashable
import Data.HashMap.Strict ( HashMap )
import qualified Data.HashMap.Strict as HM
import qualified Data.HashSet as HS

import Data.LLVM
import Data.LLVM.CFG
import Data.LLVM.CallGraph
import Data.LLVM.Analysis.CallGraphSCCTraversal
import Data.LLVM.Analysis.Dataflow
import Data.LLVM.Internal.PatriciaTree

-- | The types of nodes in the graph
data EscapeNode = VariableNode !Value
                | OParameterNode !Value
                | OGlobalNode !Value
                | OReturnNode !Value
                | INode !Value -- Allocas and allocators
                | IVirtual !Value
                deriving (Eq, Ord)

data AccessType = Direct
                | Array
                | Field !Int !Type
                deriving (Eq, Ord)

-- | Edges labels for the points-to escape graph.  These differentiate
-- between internal and external edges.
data EscapeEdge = IEdge !AccessType
                | OEdge !AccessType
                deriving (Eq, Ord)

-- | A type synonym for the underlying points-to escape graph
type PTEGraph = Gr EscapeNode EscapeEdge

-- | The escape graph that is constructed for each program point.
-- They should all share considerable structure.<commit_msg>Add an accessor to the EscapeNode to easily get the Value at each node.<commit_after>{-# LANGUAGE ViewPatterns, BangPatterns, FlexibleInstances, MultiParamTypeClasses #-}
-- | This module implements the compositional pointer/escape analysis
-- described by <NAME> (http://doi.acm.org/10.1145/320384.320400).
--
-- This version is adapted to the LLVM IR (originally for Java).
--
-- Each program variable has a VariableNode to enable lookups easily
-- during the analysis (the ID in the graph is the ID of the LLVM IR
-- object).  Each VariableNode has a corresponding location that it
-- represents (either an internal node or an external node).  The
-- types of each node correspond to those in the bitcode.  The
-- location node for a VariableNode has an ID that is the negated ID
-- of the corresponding name.
--
-- Memoize the representative field GEP for each operation by caching
-- the deduced value in the EscapeGraph structure.
--
-- Add a sequence number to the EscapeGraph and increment it whenever
-- edges are added or removed.  This should make graph equality tests
-- much faster.
module Data.LLVM.Analysis.Escape (
  -- * Types
  EscapeResult,
  EscapeGraph(..),
  EscapeNode(..),
  EscapeEdge(..),
  PTEGraph,
  -- * Functions
  runEscapeAnalysis,
  escapeGraphAtLocation,
  localPointsTo,
  valueEscaped,
  valueProperlyEscaped,
  valueWillEscape,
  -- * Debugging
  viewEscapeGraph
  ) where

import Algebra.Lattice
import Data.Graph.Inductive hiding ( Gr )
import Data.GraphViz
import Data.List ( foldl', mapAccumR )
import Data.Map ( Map )
import qualified Data.Map as M
import Data.Set ( Set, (\\) )
import qualified Data.Set as S
import Data.Hashable
import Data.HashMap.Strict ( HashMap )
import qualified Data.HashMap.Strict as HM
import qualified Data.HashSet as HS

import Data.LLVM
import Data.LLVM.CFG
import Data.LLVM.CallGraph
import Data.LLVM.Analysis.CallGraphSCCTraversal
import Data.LLVM.Analysis.Dataflow
import Data.LLVM.Internal.PatriciaTree

-- | The types of nodes in the graph
data EscapeNode = VariableNode { escapeNodeValue :: !Value }
                | OParameterNode { escapeNodeValue :: !Value }
                | OGlobalNode { escapeNodeValue :: !Value }
                | OReturnNode { escapeNodeValue :: !Value }
                | INode { escapeNodeValue :: !Value } -- Allocas and allocators
                | IVirtual { escapeNodeValue :: !Value }
                deriving (Eq, Ord)

data AccessType = Direct
                | Array
                | Field !Int !Type
                deriving (Eq, Ord)

-- | Edges labels for the points-to escape graph.  These differentiate
-- between internal and external edges.
data EscapeEdge = IEdge !AccessType
                | OEdge !AccessType
                deriving (Eq, Ord)

-- | A type synonym for the underlying points-to escape graph
type PTEGraph = Gr EscapeNode EscapeEdge

-- | The escape graph that is constructed for each program point.
-- They should all share considerable structure.
{'fraction_non_alphanumeric': 0.07955133735979293, 'fraction_numerical': 0.006212251941328731, 'mean_word_length': 2.96986301369863, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5087064', 'n_tokens_mistral': 1667, 'n_tokens_neox': 1588, 'n_words': 627}