ddc-core-llvm-0.4.2.2: Disciplined Disciple Compiler LLVM code generator.

Safe Haskell Safe Haskell98

DDC.Core.Llvm.Metadata.Graph

Synopsis

# Graphs and Trees for TBAA metadata

newtype UG a Source

An undirected graph.

Constructors

 UG (Dom a, Rel a)

Instances

 Show a => Show (UG a) Source

newtype DG a Source

A directed graph.

Constructors

 DG (Dom a, Rel a)

Instances

 Show a => Eq (DG a) Source Show a => Show (DG a) Source

orientUG :: (Show a, Ord a) => UG a -> DG a Source

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

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

newtype Tree a Source

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

Constructors

 Tree (Dom a, Rel a)

Instances

 Show a => Show (Tree a) Source

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

Get the sources of a tree.

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

Enroot a tree with the given root.

# Quickcheck Testing ONLY

type Dom a = [a] Source

type Rel a = a -> a -> Bool Source

A binary relation.

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

Convert a list to a relation.

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

Convert a relation.

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

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

transOrient :: (Show a, Ord a) => UG a -> DG a Source

Transitively orient an undireted graph

Using the algorithm from "Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing", R. McConnell et al 2000

In the case where the transitive orientation does not exist, it simply gives some orientation

note: gave up on modular decomposition, this approach has very slightly worse time complexity but much simpler

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

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 Source

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