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 /MLRISC/trunk/ra/raBitset.sml
ViewVC logotype

Annotation of /MLRISC/trunk/ra/raBitset.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2126 - (view) (download)

1 : monnier 245 (* 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 : monnier 411 val delete : bitMatrix -> (int * int) -> bool
24 :     (* val clear : bitMatrix * int -> unit
25 : monnier 245 *)
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 : monnier 429 shift : word}
39 : monnier 245 val itow = Word.fromInt
40 :     val wtoi = Word.toInt
41 :     fun roundsize size = let
42 :     fun f(x, shift) =
43 :     if x >= size then (x, Word.>>(shift, 0w1))
44 :     else f(x*2, Word.+(shift,0w1))
45 :     in f(64, 0w6)
46 :     end
47 :    
48 :     fun new size = let
49 :     val (tblSize, shift) = roundsize size
50 :     val tbl = Array.array(tblSize,NIL)
51 :     in (* note: size is offset by 1 *)
52 :     INTPAIRMAP{table = ref tbl,
53 :     elems = ref 0,
54 :     size = ref(itow(tblSize-1)),
55 : monnier 429 shift = shift}
56 : monnier 245 end
57 :    
58 :     fun moduloSize(i, j, shift, sz) =
59 :     Word.toIntX
60 :     (Word.andb
61 :     (Word.+(Word.<<(itow i, shift), itow j),
62 :     sz))
63 :    
64 :     fun member(INTPAIRMAP{table,elems,size,shift,...}) (i,j) = let
65 :     fun find NIL = false
66 :     | find(B(i',j',b)) = (i=i' andalso j=j') orelse find b
67 :     in find(Array.sub(!table, moduloSize(i, j, shift, !size)))
68 :     end
69 :    
70 :     fun add (t as INTPAIRMAP{table,elems,size,shift,...}) (v as (i,j)) = let
71 :     val ref tbl = table
72 :     val ref sz = size
73 :     val isz = wtoi sz
74 :     in
75 :     if !elems <> isz then let
76 :     val indx = moduloSize(i, j, shift, sz)
77 :     fun find NIL = false
78 :     | find(B(i',j',r)) = (i=i' andalso j=j') orelse find r
79 :     val b = Array.sub(tbl,indx)
80 :     in
81 :     if find b then false
82 :     else (Unsafe.Array.update(tbl,indx,B(i,j,b));
83 :     elems := !elems + 1;
84 :     true)
85 :     end
86 :     else let
87 :     val newsize=isz+isz+2
88 :     val new = Array.array(newsize,NIL)
89 :     val newsize1 = itow(newsize-1)
90 :     fun redo n = let
91 :     fun add'(a,b,B(i,j,r)) =
92 :     if moduloSize(i, j, shift, newsize1) = n then
93 :     add'(B(i,j,a),b,r)
94 :     else add'(a,B(i,j,b),r)
95 :     | add'(a,b,NIL) =
96 :     (Array.update(new,n,a);
97 :     Array.update(new,n+isz+1,b);
98 :     redo(n+1))
99 :     in add'(NIL, NIL, Array.sub(tbl,n))
100 :     end
101 :     in
102 :     table:=new;
103 :     size:=itow(newsize-1);
104 :     redo 0 handle _ => ();
105 :     add t v
106 :     end
107 :     end
108 :    
109 :     fun delete(INTPAIRMAP{table=ref table,elems,size,shift,...}) (i,j) = let
110 :     fun find NIL = NIL
111 :     | find(B(i',j',b)) =
112 :     if i=i' andalso j=j' then (elems := !elems-1; b) else B(i',j',find b)
113 :     val indx = moduloSize(i, j, shift, !size)
114 : monnier 411 val n = !elems
115 :     in Unsafe.Array.update(table, indx, find(Array.sub(table,indx)));
116 :     !elems <> n (* changed? *)
117 : monnier 245 end
118 :    
119 :     end
120 :    

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