my coalescer

Henry Cejtin henry@research.nj.nec.com
Mon, 10 May 1999 17:37:12 -0400


The only changes I did (which were all in equivalence-graph.fun) were:

I  deleted  the unused version of Class and the t, new, newClass, addEdge, ==
and greedy defined first.

I replaced the old definition of greedy with the following  (grotesque  hack)
code:

(*
 * Given an edge, return how desirable it is to merge the endpoints
 * of the edge.  The result is an int option because we return
 * NONE if they are not mergable.
 * Note, it looks at the details inside Class, but the whole thing
 * is just a hack.
 *)
fun goodness (Class.T lhs: Class.t, Class.T rhs: Class.t): int option =
       if Set.equals (lhs, rhs)
	  then NONE
	  else let val {size = ref lsize, ...} = Set.value lhs
		   val {size = ref rsize, ...} = Set.value rhs
	       in SOME (~ (lsize + rsize))
	       end

fun findBest (edges: (Class.t * Class.t) list)
	     : (Class.t * Class.t) option =
       let fun folder (e: Class.t * Class.t,
                       ac: (int * (Class.t * Class.t)) option) =
                  case goodness e of
                     NONE => ac
                     | SOME g =>
                          case ac of
                             NONE => SOME (g, e)
                             | SOME (g', _) =>
                                  if g > g'
                                     then SOME (g, e)
                                     else ac
       in case List.fold (edges, NONE, folder) of
	     NONE => NONE
	     | SOME (goodness, e) => (
					print ("\nHCC:\tgoodness " ^
					       Int.toString goodness ^
					       "\n");
					SOME e
				     )
       end

fun greedy {graph = T {edges, ...}, maxClassSize} =
       let fun loop () =
		  case findBest (! edges) of
		     NONE => ()
		     | SOME (lhs, rhs) =>
			  if Class.size lhs + Class.size rhs <= maxClassSize
			     then (
				     Class.== (lhs, rhs);
				     loop ()
				  )
			     else ()
       in loop ()
       end