<commit_before>{-# LANGUAGE TemplateHaskell #-}
-- | Control Dependence Graphs for the LLVM IR
--
-- This module follows the definition of control dependence of Cytron et al
-- (http://dl.acm.org/citation.cfm?doid=115372.115320):
--
-- Let X and Y be nodes in the CFG.  If X appears on every path from Y
-- to Exit, then X postdominates Y.  If X postdominates Y but X != Y,
-- then X strictly postdominates Y.
--
-- A CFG node Y is control dependent on a CFG node X if both:
--
--  * There is a non-null path p from X->Y such that Y postdominates
--    every node *after* X on p.
--
--  * The node Y does not strictly postdominate the node X.
--
-- This CDG formulation does not insert a dummy Start node to link
-- together all of the top-level nodes.  This just means that the set
-- of control dependencies can be empty if code will be executed
-- unconditionally.
module Data.LLVM.Analysis.CDG (
  -- * Types
  CDG(cdgCFG),
  -- * Constructor
  controlDependenceGraph,
  -- * Queries
  controlDependencies,
  controlDependentOn,
  -- * Visualization
  cdgGraphvizRepr
  ) where

import Control.Arrow
import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.Query.DFS
import Data.GraphViz
import Data.HashMap.Strict ( HashMap )
import qualified Data.HashMap.Strict as M
import Data.HashSet ( HashSet )
import qualified Data.HashSet as S
import Data.List ( foldl' )
import FileLocation

import Data.LLVM
import Data.LLVM.Analysis.CFG
import Data.LLVM.Analysis.Dominance
import Data.LLVM.Internal.PatriciaTree

-- | The internal representation of the CDG.  Instructions are
-- control-dependent on other instructions, so they are the nodes in
-- the graph.
type CDGType = Gr Instruction ()

-- | A control depenence graph
data CDG = CDG { cdgGraph :: CDGType
               , cdgCFG :: CFG
               }

-- | Return True if @n@ is control dependent on @m@.
--
-- > controlDependentOn cdg m n
controlDependentOn :: CDG -> Instruction -> Instruction -> Bool
controlDependentOn cdg m n = m `elem` controlDependencies cdg n

-- | Get the list of instructions that @i@ is control dependent upon.
-- This list does not include @i@.  As noted above, the list will be
-- empty if @i@ is executed unconditionally.
--
-- > controlDependences cdg i
controlDependencies :: CDG -> Instruction -> [Instruction]
controlDependencies (CDG g _) i =
  case deps of
    _ : rest -> rest
    _ -> $err' $ "Instruction should at least be reachable from itself: " ++ show i
  where
    deps = map ($fromJst . lab g) $ dfs [instructionUniqueId i] g

-- | Construct the control dependence graph for a function (from its
-- CFG).  This follows the construction from chapter 9 of the
-- Munchnick Compiler Design and Implementation book.
--
-- For an input function F:
--
-- 1) Construct the CFG G for F
--
-- 2) Construct the postdominator tree PT for F
--
-- 3) Let S be the set of edges m->n in G such that n does not
--    postdominate m
--
-- 4) For each edge m->n in S, find the lowest common ancestor l of m
--    and n in the postdominator tree.  All nodes on the path from
--    l->n (not including l) in PT are control dependent on m.<commit_msg>Add another CDG accessor<commit_after>{-# LANGUAGE TemplateHaskell #-}
-- | Control Dependence Graphs for the LLVM IR
--
-- This module follows the definition of control dependence of Cytron et al
-- (http://dl.acm.org/citation.cfm?doid=115372.115320):
--
-- Let X and Y be nodes in the CFG.  If X appears on every path from Y
-- to Exit, then X postdominates Y.  If X postdominates Y but X != Y,
-- then X strictly postdominates Y.
--
-- A CFG node Y is control dependent on a CFG node X if both:
--
--  * There is a non-null path p from X->Y such that Y postdominates
--    every node *after* X on p.
--
--  * The node Y does not strictly postdominate the node X.
--
-- This CDG formulation does not insert a dummy Start node to link
-- together all of the top-level nodes.  This just means that the set
-- of control dependencies can be empty if code will be executed
-- unconditionally.
module Data.LLVM.Analysis.CDG (
  -- * Types
  CDG(cdgCFG),
  -- * Constructor
  controlDependenceGraph,
  -- * Queries
  directControlDependencies,
  controlDependencies,
  controlDependentOn,
  -- * Visualization
  cdgGraphvizRepr
  ) where

import Control.Arrow
import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.Query.DFS
import Data.GraphViz
import Data.HashMap.Strict ( HashMap )
import qualified Data.HashMap.Strict as M
import Data.HashSet ( HashSet )
import qualified Data.HashSet as S
import Data.List ( foldl' )
import FileLocation

import Data.LLVM
import Data.LLVM.Analysis.CFG
import Data.LLVM.Analysis.Dominance
import Data.LLVM.Internal.PatriciaTree

-- | The internal representation of the CDG.  Instructions are
-- control-dependent on other instructions, so they are the nodes in
-- the graph.
type CDGType = Gr Instruction ()

-- | A control depenence graph
data CDG = CDG { cdgGraph :: CDGType
               , cdgCFG :: CFG
               }

-- | Return True if @n@ is control dependent on @m@.
--
-- > controlDependentOn cdg m n
controlDependentOn :: CDG -> Instruction -> Instruction -> Bool
controlDependentOn cdg m n = m `elem` controlDependencies cdg n

-- | Get the list of instructions that @i@ is control dependent upon.
-- This list does not include @i@.  As noted above, the list will be
-- empty if @i@ is executed unconditionally.
--
-- > controlDependences cdg i
controlDependencies :: CDG -> Instruction -> [Instruction]
controlDependencies (CDG g _) i =
  case deps of
    _ : rest -> rest
    _ -> $err' $ "Instruction should at least be reachable from itself: " ++ show i
  where
    deps = map ($fromJst . lab g) $ dfs [instructionUniqueId i] g

-- | Get the list of instructions that @i@ is directly control
-- dependent upon.
directControlDependencies :: CDG -> Instruction -> [Instruction]
directControlDependencies (CDG g _) i =
  map ($fromJst . lab g) $ suc g (instructionUniqueId i)

-- | Construct the control dependence graph for a function (from its
-- CFG).  This follows the construction from chapter 9 of the
-- Munchnick Compiler Design and Implementation book.
--
-- For an input function F:
--
-- 1) Construct the CFG G for F
--
-- 2) Construct the postdominator tree PT for F
--
-- 3) Let S be the set of edges m->n in G such that n does not
--    postdominate m
--
-- 4) For each edge m->n in S, find the lowest common ancestor l of m
--    and n in the postdominator tree.  All nodes on the path from
--    l->n (not including l) in PT are control dependent on m.
{'fraction_non_alphanumeric': 0.09401188480877648, 'fraction_numerical': 0.005180557671796434, 'mean_word_length': 3.0220588235294117, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 31, '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': '3719192', 'n_tokens_mistral': 2024, 'n_tokens_neox': 1961, 'n_words': 863}