<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <!--Rendered using the Haskell Html Library v0.2--> <HTML ><HEAD ><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8" ><TITLE >GraphBase</TITLE ><LINK HREF="haddock.css" REL="stylesheet" TYPE="text/css" ><SCRIPT SRC="haddock-util.js" TYPE="text/javascript" ></SCRIPT ><SCRIPT TYPE="text/javascript" >window.onload = function () {setSynopsis("mini_GraphBase.html")};</SCRIPT ></HEAD ><BODY ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="topbar" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD ><IMG SRC="haskell_icon.gif" WIDTH="16" HEIGHT="16" ALT=" " ></TD ><TD CLASS="title" >ghc-6.12.3: The GHC API</TD ><TD CLASS="topbut" ><A HREF="index.html" >Contents</A ></TD ><TD CLASS="topbut" ><A HREF="doc-index.html" >Index</A ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="modulebar" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD ><FONT SIZE="6" >GraphBase</FONT ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" >Description</TD ></TR ><TR ><TD CLASS="doc" >Types for the general graph colorer. </TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" >Synopsis</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >type</SPAN > <A HREF="#t%3ATriv" >Triv</A > k cls color = cls -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > k -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > color -> <A HREF="../base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A ></TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A HREF="#t%3AGraph" >Graph</A > k cls color = <A HREF="#v%3AGraph" >Graph</A > {<TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="recfield" ><A HREF="#v%3AgraphMap" >graphMap</A > :: <A HREF="UniqFM.html#t%3AUniqFM" >UniqFM</A > (<A HREF="GraphBase.html#t%3ANode" >Node</A > k cls color)</TD ></TR ></TABLE >}</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AinitGraph" >initGraph</A > :: <A HREF="GraphBase.html#t%3AGraph" >Graph</A > k cls color</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AgraphMapModify" >graphMapModify</A > :: (<A HREF="UniqFM.html#t%3AUniqFM" >UniqFM</A > (<A HREF="GraphBase.html#t%3ANode" >Node</A > k cls color) -> <A HREF="UniqFM.html#t%3AUniqFM" >UniqFM</A > (<A HREF="GraphBase.html#t%3ANode" >Node</A > k cls color)) -> <A HREF="GraphBase.html#t%3AGraph" >Graph</A > k cls color -> <A HREF="GraphBase.html#t%3AGraph" >Graph</A > k cls color</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A HREF="#t%3ANode" >Node</A > k cls color = <A HREF="#v%3ANode" >Node</A > {<TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="recfield" ><A HREF="#v%3AnodeId" >nodeId</A > :: k</TD ></TR ><TR ><TD CLASS="recfield" ><A HREF="#v%3AnodeClass" >nodeClass</A > :: cls</TD ></TR ><TR ><TD CLASS="recfield" ><A HREF="#v%3AnodeColor" >nodeColor</A > :: <A HREF="../base-4.2.0.2/Data-Maybe.html#t%3AMaybe" >Maybe</A > color</TD ></TR ><TR ><TD CLASS="recfield" ><A HREF="#v%3AnodeConflicts" >nodeConflicts</A > :: <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > k</TD ></TR ><TR ><TD CLASS="recfield" ><A HREF="#v%3AnodeExclusions" >nodeExclusions</A > :: <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > color</TD ></TR ><TR ><TD CLASS="recfield" ><A HREF="#v%3AnodePreference" >nodePreference</A > :: [color]</TD ></TR ><TR ><TD CLASS="recfield" ><A HREF="#v%3AnodeCoalesce" >nodeCoalesce</A > :: <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > k</TD ></TR ></TABLE >}</TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3AnewNode" >newNode</A > :: k -> cls -> <A HREF="GraphBase.html#t%3ANode" >Node</A > k cls color</TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" >Documentation</TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >type</SPAN > <A NAME="t:Triv" ><A NAME="t%3ATriv" ></A ></A ><B >Triv</B > k cls color = cls -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > k -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > color -> <A HREF="../base-4.2.0.2/Data-Bool.html#t%3ABool" >Bool</A ></TD ></TR ><TR ><TD CLASS="doc" ><P >A fn to check if a node is trivially colorable For graphs who's color classes are disjoint then a node is 'trivially colorable' when it has less neighbors and exclusions than available colors for that node. </P ><P >For graph's who's color classes overlap, ie some colors alias other colors, then this can be a bit more tricky. There is a general way to calculate this, but it's likely be too slow for use in the code. The coloring algorithm takes a canned function which can be optimised by the user to be specific to the specific graph being colored. </P ><P >for details, see <A HREF="A Generalised Algorithm for Graph-Coloring Register Allocation.html" >A Generalised Algorithm for Graph-Coloring Register Allocation</A > Smith, Ramsey, Holloway - PLDI 2004. </P ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A NAME="t:Graph" ><A NAME="t%3AGraph" ></A ></A ><B >Graph</B > k cls color </TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="ndoc" >The Interference graph. There used to be more fields, but they were turfed out in a previous revision. maybe we'll want more later.. </TD ></TR ><TR ><TD CLASS="section4" >Constructors</TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="5" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:Graph" ><A NAME="v%3AGraph" ></A ></A ><B >Graph</B ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="body" COLSPAN="2" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:graphMap" ><A NAME="v%3AgraphMap" ></A ></A ><B >graphMap</B > :: <A HREF="UniqFM.html#t%3AUniqFM" >UniqFM</A > (<A HREF="GraphBase.html#t%3ANode" >Node</A > k cls color)</TD ><TD CLASS="rdoc" >All active nodes in the graph. </TD ></TR ></TABLE ></TD ></TR ></TABLE ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:initGraph" ><A NAME="v%3AinitGraph" ></A ></A ><B >initGraph</B > :: <A HREF="GraphBase.html#t%3AGraph" >Graph</A > k cls color</TD ></TR ><TR ><TD CLASS="doc" >An empty graph. </TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:graphMapModify" ><A NAME="v%3AgraphMapModify" ></A ></A ><B >graphMapModify</B > :: (<A HREF="UniqFM.html#t%3AUniqFM" >UniqFM</A > (<A HREF="GraphBase.html#t%3ANode" >Node</A > k cls color) -> <A HREF="UniqFM.html#t%3AUniqFM" >UniqFM</A > (<A HREF="GraphBase.html#t%3ANode" >Node</A > k cls color)) -> <A HREF="GraphBase.html#t%3AGraph" >Graph</A > k cls color -> <A HREF="GraphBase.html#t%3AGraph" >Graph</A > k cls color</TD ></TR ><TR ><TD CLASS="doc" >Modify the finite map holding the nodes in the graph. </TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A NAME="t:Node" ><A NAME="t%3ANode" ></A ></A ><B >Node</B > k cls color </TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="ndoc" >Graph nodes. Represents a thing that can conflict with another thing. For the register allocater the nodes represent registers. </TD ></TR ><TR ><TD CLASS="section4" >Constructors</TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="5" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:Node" ><A NAME="v%3ANode" ></A ></A ><B >Node</B ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="body" COLSPAN="2" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:nodeId" ><A NAME="v%3AnodeId" ></A ></A ><B >nodeId</B > :: k</TD ><TD CLASS="rdoc" >A unique identifier for this node. </TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:nodeClass" ><A NAME="v%3AnodeClass" ></A ></A ><B >nodeClass</B > :: cls</TD ><TD CLASS="rdoc" >The class of this node, determines the set of colors that can be used. </TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:nodeColor" ><A NAME="v%3AnodeColor" ></A ></A ><B >nodeColor</B > :: <A HREF="../base-4.2.0.2/Data-Maybe.html#t%3AMaybe" >Maybe</A > color</TD ><TD CLASS="rdoc" >The color of this node, if any. </TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:nodeConflicts" ><A NAME="v%3AnodeConflicts" ></A ></A ><B >nodeConflicts</B > :: <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > k</TD ><TD CLASS="rdoc" >Neighbors which must be colored differently to this node. </TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:nodeExclusions" ><A NAME="v%3AnodeExclusions" ></A ></A ><B >nodeExclusions</B > :: <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > color</TD ><TD CLASS="rdoc" >Colors that cannot be used by this node. </TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:nodePreference" ><A NAME="v%3AnodePreference" ></A ></A ><B >nodePreference</B > :: [color]</TD ><TD CLASS="rdoc" >Colors that this node would prefer to be, in decending order. </TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:nodeCoalesce" ><A NAME="v%3AnodeCoalesce" ></A ></A ><B >nodeCoalesce</B > :: <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > k</TD ><TD CLASS="rdoc" >Neighbors that this node would like to be colored the same as. </TD ></TR ></TABLE ></TD ></TR ></TABLE ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:newNode" ><A NAME="v%3AnewNode" ></A ></A ><B >newNode</B > :: k -> cls -> <A HREF="GraphBase.html#t%3ANode" >Node</A > k cls color</TD ></TR ><TR ><TD CLASS="doc" >An empty node. </TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="botbar" >Produced by <A HREF="http://www.haskell.org/haddock/" >Haddock</A > version 2.6.1</TD ></TR ></TABLE ></BODY ></HTML >