<!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 >RegAlloc.Graph.ArchBase</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_RegAlloc-Graph-ArchBase.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" >RegAlloc.Graph.ArchBase</FONT ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="section1" >Description</TD ></TR ><TR ><TD CLASS="doc" ><P >Utils for calculating general worst, bound, squeese and free, functions. </P ><P >as per: <A HREF="A Generalized Algorithm for Graph-Coloring Register Allocation.html" >A Generalized Algorithm for Graph-Coloring Register Allocation</A > Michael Smith, Normal Ramsey, Glenn Holloway. PLDI 2004 </P ><P >These general versions are not used in GHC proper because they are too slow. Instead, hand written optimised versions are provided for each architecture in MachRegs*.hs </P ><P >This code is here because we can test the architecture specific code against it. </P ></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" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A HREF="#t%3ARegClass" >RegClass</A > </TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" >= <A HREF="#v%3AClassG32" >ClassG32</A ></TD ></TR ><TR ><TD CLASS="decl" >| <A HREF="#v%3AClassG16" >ClassG16</A ></TD ></TR ><TR ><TD CLASS="decl" >| <A HREF="#v%3AClassG8" >ClassG8</A ></TD ></TR ><TR ><TD CLASS="decl" >| <A HREF="#v%3AClassF64" >ClassF64</A ></TD ></TR ></TABLE ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A HREF="#t%3AReg" >Reg</A > </TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" >= <A HREF="#v%3AReg" >Reg</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > <A HREF="../base-4.2.0.2/Data-Int.html#t%3AInt" >Int</A ></TD ></TR ><TR ><TD CLASS="decl" >| <A HREF="#v%3ARegSub" >RegSub</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegSub" >RegSub</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A ></TD ></TR ></TABLE ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A HREF="#t%3ARegSub" >RegSub</A > </TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="decl" >= <A HREF="#v%3ASubL16" >SubL16</A ></TD ></TR ><TR ><TD CLASS="decl" >| <A HREF="#v%3ASubL8" >SubL8</A ></TD ></TR ><TR ><TD CLASS="decl" >| <A HREF="#v%3ASubL8H" >SubL8H</A ></TD ></TR ></TABLE ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Aworst" >worst</A > :: (<A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A >) -> (<A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A > -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A >) -> <A HREF="../base-4.2.0.2/Data-Int.html#t%3AInt" >Int</A > -> <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> <A HREF="../base-4.2.0.2/Data-Int.html#t%3AInt" >Int</A ></TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Abound" >bound</A > :: (<A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A >) -> (<A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A > -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A >) -> <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> [<A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A >] -> <A HREF="../base-4.2.0.2/Data-Int.html#t%3AInt" >Int</A ></TD ></TR ><TR ><TD CLASS="s8" ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="#v%3Asqueese" >squeese</A > :: (<A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A >) -> (<A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A > -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A >) -> <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> [(<A HREF="../base-4.2.0.2/Data-Int.html#t%3AInt" >Int</A >, <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A >)] -> <A HREF="../base-4.2.0.2/Data-Int.html#t%3AInt" >Int</A ></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" >data</SPAN > <A NAME="t:RegClass" ><A NAME="t%3ARegClass" ></A ></A ><B >RegClass</B > </TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="section4" >Constructors</TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:ClassG32" ><A NAME="v%3AClassG32" ></A ></A ><B >ClassG32</B ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:ClassG16" ><A NAME="v%3AClassG16" ></A ></A ><B >ClassG16</B ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:ClassG8" ><A NAME="v%3AClassG8" ></A ></A ><B >ClassG8</B ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:ClassF64" ><A NAME="v%3AClassF64" ></A ></A ><B >ClassF64</B ></TD ><TD CLASS="rdoc" ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="section4" ><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:RegClass')" ALT="show/hide" > Instances</TD ></TR ><TR ><TD CLASS="body" ><DIV ID="i:RegClass" STYLE="display:block;" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="decl" ><A HREF="../base-4.2.0.2/Prelude.html#t%3AEnum" >Enum</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="../base-4.2.0.2/Data-Eq.html#t%3AEq" >Eq</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="../base-4.2.0.2/Text-Show.html#t%3AShow" >Show</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A ></TD ></TR ></TABLE ></DIV ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A NAME="t:Reg" ><A NAME="t%3AReg" ></A ></A ><B >Reg</B > </TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="ndoc" >A register of some class </TD ></TR ><TR ><TD CLASS="section4" >Constructors</TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:Reg" ><A NAME="v%3AReg" ></A ></A ><B >Reg</B > <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > <A HREF="../base-4.2.0.2/Data-Int.html#t%3AInt" >Int</A ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:RegSub" ><A NAME="v%3ARegSub" ></A ></A ><B >RegSub</B > <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegSub" >RegSub</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A ></TD ><TD CLASS="rdoc" ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="section4" ><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:Reg')" ALT="show/hide" > Instances</TD ></TR ><TR ><TD CLASS="body" ><DIV ID="i:Reg" STYLE="display:block;" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="decl" ><A HREF="../base-4.2.0.2/Data-Eq.html#t%3AEq" >Eq</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="../base-4.2.0.2/Text-Show.html#t%3AShow" >Show</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="Unique.html#t%3AUniquable" >Uniquable</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A ></TD ></TR ></TABLE ></DIV ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><SPAN CLASS="keyword" >data</SPAN > <A NAME="t:RegSub" ><A NAME="t%3ARegSub" ></A ></A ><B >RegSub</B > </TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="0" CELLPADDING="0" ><TR ><TD CLASS="ndoc" >A subcomponent of another register </TD ></TR ><TR ><TD CLASS="section4" >Constructors</TD ></TR ><TR ><TD CLASS="body" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="arg" ><A NAME="v:SubL16" ><A NAME="v%3ASubL16" ></A ></A ><B >SubL16</B ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:SubL8" ><A NAME="v%3ASubL8" ></A ></A ><B >SubL8</B ></TD ><TD CLASS="rdoc" ></TD ></TR ><TR ><TD CLASS="arg" ><A NAME="v:SubL8H" ><A NAME="v%3ASubL8H" ></A ></A ><B >SubL8H</B ></TD ><TD CLASS="rdoc" ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="section4" ><IMG SRC="minus.gif" CLASS="coll" ONCLICK="toggle(this,'i:RegSub')" ALT="show/hide" > Instances</TD ></TR ><TR ><TD CLASS="body" ><DIV ID="i:RegSub" STYLE="display:block;" ><TABLE CLASS="vanilla" CELLSPACING="1" CELLPADDING="0" ><TR ><TD CLASS="decl" ><A HREF="../base-4.2.0.2/Prelude.html#t%3AEnum" >Enum</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegSub" >RegSub</A ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="../base-4.2.0.2/Data-Eq.html#t%3AEq" >Eq</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegSub" >RegSub</A ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="../base-4.2.0.2/Data-Ord.html#t%3AOrd" >Ord</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegSub" >RegSub</A ></TD ></TR ><TR ><TD CLASS="decl" ><A HREF="../base-4.2.0.2/Text-Show.html#t%3AShow" >Show</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegSub" >RegSub</A ></TD ></TR ></TABLE ></DIV ></TD ></TR ></TABLE ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:worst" ><A NAME="v%3Aworst" ></A ></A ><B >worst</B > :: (<A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A >) -> (<A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A > -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A >) -> <A HREF="../base-4.2.0.2/Data-Int.html#t%3AInt" >Int</A > -> <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> <A HREF="../base-4.2.0.2/Data-Int.html#t%3AInt" >Int</A ></TD ></TR ><TR ><TD CLASS="doc" ><P >Worst case displacement </P ><P >a node N of classN has some number of neighbors, all of which are from classC. </P ><P >(worst neighbors classN classC) is the maximum number of potential colors for N that can be lost by coloring its neighbors. </P ></TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:bound" ><A NAME="v%3Abound" ></A ></A ><B >bound</B > :: (<A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A >) -> (<A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A > -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A >) -> <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> [<A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A >] -> <A HREF="../base-4.2.0.2/Data-Int.html#t%3AInt" >Int</A ></TD ></TR ><TR ><TD CLASS="doc" >For a node N of classN and neighbors of classesC (bound classN classesC) is the maximum number of potential colors for N that can be lost by coloring its neighbors. </TD ></TR ><TR ><TD CLASS="s15" ></TD ></TR ><TR ><TD CLASS="decl" ><A NAME="v:squeese" ><A NAME="v%3Asqueese" ></A ></A ><B >squeese</B > :: (<A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A >) -> (<A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A > -> <A HREF="UniqSet.html#t%3AUniqSet" >UniqSet</A > <A HREF="RegAlloc-Graph-ArchBase.html#t%3AReg" >Reg</A >) -> <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A > -> [(<A HREF="../base-4.2.0.2/Data-Int.html#t%3AInt" >Int</A >, <A HREF="RegAlloc-Graph-ArchBase.html#t%3ARegClass" >RegClass</A >)] -> <A HREF="../base-4.2.0.2/Data-Int.html#t%3AInt" >Int</A ></TD ></TR ><TR ><TD CLASS="doc" ><P >The total squeese on a particular node with a list of neighbors. </P ><P >A version of this should be constructed for each particular architecture, possibly including uses of bound, so that alised registers don't get counted twice, as per the paper. </P ></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 >