Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/branches/SMLNJ/src/MLRISC/mlrisc/raBitset.sml
ViewVC logotype

Annotation of /sml/branches/SMLNJ/src/MLRISC/mlrisc/raBitset.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 223 - (view) (download)

1 : monnier 16 (* raBitset.sml
2 :     *
3 :     * COPYRIGHT (c) 1995 AT&T Bell Laboratories.
4 :     *
5 :     * Imperative bitsets.
6 :     *
7 :     * This has been written specially for the register allocator.
8 :     * The computation of n(n+1)/2 very quickly overflows in practice.
9 :     *
10 :     *)
11 :    
12 :     (** This has been written specially for the register allocator.
13 :     ** We use a hash table representation, because it performs better
14 :     ** than a linear representation except for small numbers of live
15 :     ** ranges.
16 :     **)
17 :    
18 :     signature BITMATRIX = sig
19 :     type bitMatrix
20 :     val new : int -> bitMatrix
21 :     val add : bitMatrix -> (int * int) -> bool
22 :     val member : bitMatrix -> (int * int) -> bool
23 :     (* val delete : bitMatrix -> (int * int) -> unit
24 :     val clear : bitMatrix * int -> unit
25 :     *)
26 :     end
27 :    
28 :    
29 :     structure TriangularBitMatrix :> BITMATRIX =
30 :     struct
31 :    
32 :     datatype bucket = NIL | B of (int * int * bucket)
33 :    
34 :     datatype bitMatrix =
35 :     INTPAIRMAP of {table : bucket Array.array ref,
36 :     elems : int ref,
37 :     size : word ref,
38 :     shift : word,
39 :     original : bucket Array.array}
40 :     val itow = Word.fromInt
41 :     val wtoi = Word.toInt
42 :     fun roundsize size = let
43 :     fun f(x, shift) =
44 :     if x >= size then (x, Word.>>(shift, 0w1))
45 :     else f(x*2, Word.+(shift,0w1))
46 :     in f(64, 0w6)
47 :     end
48 :    
49 :     fun new size = let
50 :     val (tblSize, shift) = roundsize size
51 :     val tbl = Array.array(tblSize,NIL)
52 :     in (* note: size is offset by 1 *)
53 :     INTPAIRMAP{table = ref tbl,
54 :     elems = ref 0,
55 :     size = ref(itow(tblSize-1)),
56 :     shift = shift,
57 :     original = tbl}
58 :     end
59 :    
60 :     fun moduloSize(i, j, shift, sz) =
61 :     Word.toIntX
62 :     (Word.andb
63 :     (Word.+(Word.<<(itow i, shift), itow j),
64 :     sz))
65 :    
66 :     fun member(INTPAIRMAP{table,elems,size,shift,...}) (i,j) = let
67 :     fun find NIL = false
68 :     | find(B(i',j',b)) = (i=i' andalso j=j') orelse find b
69 :     in find(Array.sub(!table, moduloSize(i, j, shift, !size)))
70 :     end
71 :    
72 :     fun add (t as INTPAIRMAP{table,elems,size,shift,...}) (v as (i,j)) = let
73 :     val ref tbl = table
74 :     val ref sz = size
75 :     val isz = wtoi sz
76 :     in
77 :     if !elems <> isz then let
78 :     val indx = moduloSize(i, j, shift, sz)
79 :     fun find NIL = false
80 :     | find(B(i',j',r)) = (i=i' andalso j=j') orelse find r
81 :     val b = Array.sub(tbl,indx)
82 :     in
83 :     if find b then false
84 :     else (Unsafe.Array.update(tbl,indx,B(i,j,b));
85 :     elems := !elems + 1;
86 :     true)
87 :     end
88 :     else let
89 :     val newsize=isz+isz+2
90 :     val new = Array.array(newsize,NIL)
91 :     val newsize1 = itow(newsize-1)
92 :     fun redo n = let
93 :     fun add'(a,b,B(i,j,r)) =
94 :     if moduloSize(i, j, shift, newsize1) = n then
95 :     add'(B(i,j,a),b,r)
96 :     else add'(a,B(i,j,b),r)
97 :     | add'(a,b,NIL) =
98 :     (Array.update(new,n,a);
99 :     Array.update(new,n+isz+1,b);
100 :     redo(n+1))
101 :     in add'(NIL, NIL, Array.sub(tbl,n))
102 :     end
103 :     in
104 :     table:=new;
105 :     size:=itow(newsize-1);
106 :     redo 0 handle _ => ();
107 :     add t v
108 :     end
109 :     end
110 :    
111 :     fun delete(INTPAIRMAP{table=ref table,elems,size,shift,...}) (i,j) = let
112 :     fun find NIL = NIL
113 :     | find(B(i',j',b)) =
114 :     if i=i' andalso j=j' then (elems := !elems-1; b) else B(i',j',find b)
115 :     val indx = moduloSize(i, j, shift, !size)
116 :     in Unsafe.Array.update(table, indx, find(Array.sub(table,indx)))
117 :     end
118 :    
119 :     fun clear (INTPAIRMAP{table,elems,original,size, ...}, _) = let
120 :     fun init n = (Array.update(original,n,NIL); init(n+1))
121 :     in
122 :     elems:=0;
123 :     size:=itow(Array.length original - 1);
124 :     table:=original;
125 :     init 0 handle _ => ()
126 :     end
127 :     end
128 :    
129 :     (*
130 : monnier 223 * $Log: raBitset.sml,v $
131 :     * Revision 1.1.1.1 1998/04/08 18:39:02 george
132 :     * Version 110.5
133 :     *
134 : monnier 16 *)

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0