hipe_icode_{bincomp,range}: Improve complexity

hipe_icode_bincomp:find_bs_get_integer/3 was quadratic for no good reason. By observing
that NewSuccs and Rest are always disjoint, we can see that the worklist
does not need to be a set. Furthermore, by replacing the ordset Visited
with a map, we reduce complexity to (a very low) O(n lg n).

On cuter_binlib, this change reduced the time for hipe_icode_bincomp
from 60s to .25s. Using a gb_set for Visited gives .5s, and a sets:set
1s.

We apply the same optimisation to hipe_icode_range.

1 files changed, 22 insertions, 6 deletions

diff --git a/lib/hipe/icode/hipe_icode_bincomp.erl b/lib/hipe/icode/hipe_icode_bincomp.erl
index 5a27519141..5ee6fe2c87 100644
--- a/lib/hipe/icode/hipe_icode_bincomp.erl
+++ b/lib/hipe/icode/hipe_icode_bincomp.erl
@@ -40,8 +40,8 @@
 -spec cfg(cfg()) -> cfg().
 
 cfg(Cfg1) ->
-  StartLbls = ordsets:from_list([hipe_icode_cfg:start_label(Cfg1)]),
-  find_bs_get_integer(StartLbls, Cfg1, StartLbls).
+  StartLbl = hipe_icode_cfg:start_label(Cfg1),
+  find_bs_get_integer([StartLbl], Cfg1, set_from_list([StartLbl])).
 
 find_bs_get_integer([Lbl|Rest], Cfg, Visited) ->
   BB = hipe_icode_cfg:bb(Cfg, Lbl),
@@ -55,10 +55,10 @@ find_bs_get_integer([Lbl|Rest], Cfg, Visited) ->
        not_ok ->
 	 Cfg
      end,
-  Succs = ordsets:from_list(hipe_icode_cfg:succ(NewCfg, Lbl)),
-  NewSuccs = ordsets:subtract(Succs, Visited),
-  NewLbls = ordsets:union(NewSuccs, Rest),
-  NewVisited = ordsets:union(NewSuccs, Visited),
+  Succs = hipe_icode_cfg:succ(NewCfg, Lbl),
+  NewSuccs = not_visited(Succs, Visited),
+  NewLbls = NewSuccs ++ Rest,
+  NewVisited = set_union(set_from_list(NewSuccs), Visited),
   find_bs_get_integer(NewLbls, NewCfg, NewVisited);
 find_bs_get_integer([], Cfg, _) ->
   Cfg.
@@ -177,3 +177,19 @@ make_butlast([{Res, Size}|Rest], Var) ->
 			[Var, hipe_icode:mk_const((1 bsl Size)-1)]),
    hipe_icode:mk_primop([NewVar], 'bsr', [Var, hipe_icode:mk_const(Size)])
    |make_butlast(Rest, NewVar)].
+
+%%--------------------------------------------------------------------
+%% Sets
+
+set_from_list([]) -> #{};
+set_from_list(L) ->
+  maps:from_list([{E, []} || E <- L]).
+
+not_visited([], _) -> [];
+not_visited([E|T], M) ->
+  case M of
+    #{E := _} -> not_visited(T, M);
+    _ -> [E|not_visited(T, M)]
+  end.
+
+set_union(A, B) -> maps:merge(A, B).