DDC.Core.Llvm.Metadata.Graph

Graphs and Trees for TBAA metadata

newtype UG a

An undirected graph.

Constructors

UG (Dom a, Rel a)

Instances

Show a => Show (UG a)

newtype DG a

A directed graph.

Constructors

DG (Dom a, Rel a)

Instances

Show a => Eq (DG a)

Show a => Show (DG a)

minOrientation :: (Show a, Eq a) => UG a -> DG a

Find the orientation with the smallest transitive closure

partitionDG :: Eq a => DG a -> [Tree a]

Partition a DG into the minimum set of (directed) trees

newtype Tree a

An inverted tree (with edges going from child to parent)

Constructors

Tree (Dom a, Rel a)

Instances

Show a => Show (Tree a)

sources :: Eq a => a -> Tree a -> [a]

Get the sources of a tree.

anchor :: Eq a => a -> Tree a -> Tree a

Enroot a tree with the given root.

Quickcheck Testing ONLY

type Dom a = [a]

type Rel a = a -> a -> Bool

A binary relation.

fromList :: Eq a => [(a, a)] -> Rel a

Convert a list to a relation.

toList :: Dom a -> Rel a -> [(a, a)]

Convert a relation.

allR :: Eq a => Rel a

The universal negative relation. All members of the domain are not related.

differenceR :: Rel a -> Rel a -> Rel a

Fifference of two relations.

unionR :: Rel a -> Rel a -> Rel a

Union two relations.

composeR :: Dom a -> Rel a -> Rel a -> Rel a

Compose two relations.

transitiveR :: Dom a -> Rel a -> Bool

Check whether a relation is transitive.

transClosure :: Eq a => Dom a -> Rel a -> Rel a

Find the transitive closure of a binary relation using Floyd-Warshall algorithm

transReduction :: Eq a => Dom a -> Rel a -> Rel a

aliasMeasure :: Eq a => Rel a -> Partitioning a -> Int

Calculate the aliasing induced by a set of trees this includes aliasing within each of the trees and aliasing among trees.

isTree :: Dom a -> Rel a -> Bool

A relation is an (inverted) tree if each node has at most one outgoing arc

orientation :: Eq a => UG a -> DG a

orientations :: Eq a => UG a -> [Rel a]

bruteforceMinOrientation :: (Show a, Eq a) => UG a -> DG a

transOrientation :: Eq a => UG a -> Maybe (DG a)

Find the transitive orientation of an undirected graph if one exists

smallOrientation :: (Show a, Eq a) => UG a -> DG a

Find the orientation with a `small enough' transitive closure

partitionings :: Eq a => [a] -> [Partitioning a]

Generate all possible partitions of a list by nondeterministically decide which sublist to add an element to.

minimumCompletion :: (Show a, Eq a) => UG a -> UG a

Add a minimum number of edges to an undirected graph such that it has a transitive orientation