1% module shared_graph. /* Shape-graph with sharing information */ 2 3% export var_edge(bff). 4% export sel_edge(bfff). 5% export is_shared(bf). 6 7:- import member/2 from basics. 8 9/* Auxiliary functions ----------------------------------------------- */ 10 11singleton(X,NX) :- create_set(Temp), add_elem(X,Temp,NX). 12 13del_elem(X,NX,NY) :- singleton(X,Xset), difference(NX,Xset,NY). 14 15:- table transitively_points_to/3. 16 17transitively_points_to(U, NX, Z) :- var_edge(U, Z, NX). 18transitively_points_to(U, NX, Z) :- sel_edge(U, NY, _, NX), 19 transitively_points_to(U, NY, Z). 20 21disjoint_or_equal(X,Y) :- set_equal(X, Y). 22disjoint_or_equal(X,Y) :- inter(X, Y, []). 23 24rename_var_to_var(NT,X,Y,NZ) :- member(Y,NT), add_elem(X,NT,NZ). 25rename_var_to_var(NT,_,Y,NZ) :- not member(Y,NT), set_equal(NT, NZ). 26 27:- table var_edge/3, sel_edge/4, is_shared/2. 28 29/* Explicit Initializations */ 30var_edge(V, X, NX) :- init_var_edge(V, X, NX). 31sel_edge(V, NX1,Sel,NX2) :- init_sel_edge(V, NX1, Sel, NX2). 32is_shared(V, NX) :- init_is_shared(V, NX). 33 34/* Edges with no pointer manipulation */ 35var_edge(V,X,NX) :- identity(U, V), var_edge(U, X, NX). 36sel_edge(V,NX1,Sel,NX2) :- identity(U, V), sel_edge(U, NX1, Sel, NX2). 37is_shared(V,NX) :- identity(U, V), is_shared(U, NX). 38 39/* x := nil ------------------------------------------------------- */ 40 41var_edge(V, Y, NYP) :- 42 assign_nil_to_var(U,V,X), 43 var_edge(U, Y ,NY), 44 Y\==X, 45 del_elem(X, NY, NYP). 46sel_edge(V, NY1P, Sel, NY2P) :- 47 assign_nil_to_var(U,V,X), 48 sel_edge(U, NY1, Sel, NY2), 49 transitively_points_to(U, NY1, Y1), 50 Y1 \== X, 51 transitively_points_to(U, NY2, Y2), 52 Y2 \== X, 53 del_elem(X, NY1, NY1P), 54 del_elem(X, NY2, NY2P). 55is_shared(V, NYP) :- 56 assign_nil_to_var(U,V,X), 57 is_shared(U, NY), 58 transitively_points_to(U, NY, Y), 59 Y \== X, 60 del_elem(X, NY, NYP). 61 62/* x.sel_0 := nil ----------------------------------------------------- */ 63var_edge(V, Z, NZ) :- 64 assign_nil_to_sel(U,V,_,_Sel0), 65 var_edge(U, Z, NZ). 66 67sel_edge(V, NZ1, Sel, NZ2) :- 68 assign_nil_to_sel(U,V,_,Sel0), 69 sel_edge(U, NZ1, Sel, NZ2), 70 Sel \== Sel0. 71sel_edge(V, NZ1, Sel, NZ2) :- 72 assign_nil_to_sel(U,V,X,_Sel0), 73 sel_edge(U, NZ1, Sel, NZ2), 74 not member(X,NZ1). 75 76is_shared(V, NZ) :- 77 assign_nil_to_sel(U,V,_,_Sel0), 78 is_shared(U, NZ), 79 sel_edge(V, NZ1, _, NZ), 80 sel_edge(V, NZ2, _, NZ), 81 inter(NZ1, NZ2, []). 82is_shared(V, NZ) :- 83 assign_nil_to_sel(U,V,_,_Sel0), 84 is_shared(U, NZ), 85 sel_edge(V, NW, Sel1, NZ), 86 sel_edge(V, NW, Sel2, NZ), 87 Sel1 \== Sel2. 88 89/* x := new ------------------------------------ */ 90 91var_edge(V, Z, NZ) :- 92 assign_new_to_var(U,V,_), 93 var_edge(U, Z, NZ). 94var_edge(V, X, NX) :- /* Create the new var_edge from X */ 95 assign_new_to_var(_,V,X), 96 singleton(X,NX). 97sel_edge(V, NY, Sel, NZ) :- 98 assign_new_to_var(U,V,_), 99 sel_edge(U, NY, Sel, NZ). 100is_shared(V, NZ) :- 101 assign_new_to_var(U,V,_), 102 is_shared(U, NZ). 103 104/* x := y --------------------------- */ 105 106var_edge(V, Z, NZP) :- 107 assign_var_to_var(U,V,X,Y), 108 var_edge(U, Z, NZ), 109 rename_var_to_var(NZ,X,Y,NZP). 110var_edge(V, X, NXY) :- 111 assign_var_to_var(U,V,X,Y), 112 var_edge(U, Y, NY), 113 rename_var_to_var(NY,X,Y,NXY). 114sel_edge(V, NZ1P, Sel, NZ2P) :- 115 assign_var_to_var(U,V,X,Y), 116 sel_edge(U, NZ1, Sel, NZ2), 117 rename_var_to_var(NZ1,X,Y,NZ1P), 118 rename_var_to_var(NZ2,X,Y,NZ2P). 119is_shared(V, NZP) :- 120 assign_var_to_var(U,V,X,Y), 121 is_shared(U, NZ), 122 rename_var_to_var(NZ,X,Y,NZP). 123 124/* x := y.sel0 ---------------------------- */ 125 126var_edge(V, Z, NZ) :- 127 assign_sel_to_var(U,V,_X,_Y,_Sel0), 128 var_edge(U, Z, NZ). 129var_edge(V, X, NXZ) :- 130 assign_sel_to_var(U,V,X,Y,Sel0), 131 var_edge(U, Y, NY), 132 sel_edge(U, NY, Sel0, NZ), 133 add_elem(X,NZ,NXZ). 134var_edge(V, Z, NXZ) :- 135 assign_sel_to_var(U,V,X,Y,Sel0), 136 var_edge(U, Y, NY), 137 sel_edge(U, NY, Sel0, NZ), 138 add_elem(X,NZ,NXZ), 139 var_edge(U, Z, NZ). 140/* old -> old */ 141sel_edge(V, NZ1, Sel, NZ2) :- 142 assign_sel_to_var(U,V,_X,Y,_Sel0), 143 sel_edge(U, NZ1, Sel, NZ2), 144 not member(Y,NZ1). 145/* old -> old */ 146sel_edge(V, NZ1, Sel, NZ2) :- 147 assign_sel_to_var(U,V,_X,_Y,Sel0), 148 sel_edge(U, NZ1, Sel, NZ2), 149 Sel \== Sel0. 150/* old -> new */ 151sel_edge(V, NY, Sel0, NXZ) :- 152 assign_sel_to_var(U,V,X,Y,Sel0), 153 var_edge(U, Y, NY), 154 sel_edge(U, NY, Sel0, NZ), 155 add_elem(X,NZ,NXZ), 156 not set_equal(NY, NZ). 157% NY \== NZ. 158/* new -> old */ 159sel_edge(V, NXZ, Sel, NT) :- 160 assign_sel_to_var(U,V,X,Y,Sel0), 161 var_edge(U, Y, NY), 162 sel_edge(U, NY, Sel0, NZ), 163 add_elem(X,NZ,NXZ), 164 sel_edge(U, NZ, Sel, NT), 165 not set_equal(NZ, NY), 166% NZ \== NY, 167 disjoint_or_equal(NXZ, NT). /* Can be replaced by NZ <> NT or NZ = {} */ 168/* new -> old */ 169sel_edge(V, NXZ, Sel, NT) :- 170 assign_sel_to_var(U,V,X,Y,Sel0), 171 var_edge(U, Y, NY), 172 sel_edge(U, NY, Sel0, NZ), 173 add_elem(X,NZ,NXZ), 174 sel_edge(U, NZ, Sel, NT), 175 Sel \== Sel0, 176 disjoint_or_equal(NXZ, NT). /* Can be replaced by NZ <> NT or NZ = {} */ 177/* new -> new */ 178sel_edge(V, NXY, Sel0, NXY1) :- 179 assign_sel_to_var(U,V,X,Y,Sel0), 180 var_edge(U, Y, NY), 181 sel_edge(U, NY, Sel0, NY), 182 add_elem(X,NY,NXY), 183 set_equal(NXY, NXY1). 184/* new -> new */ 185sel_edge(V, NXZ, Sel, NXZ1) :- 186 assign_sel_to_var(U,V,X,Y,Sel0), 187 var_edge(U, Y, NY), 188 sel_edge(U, NY, Sel0, NZ), 189 is_shared(U, NZ), 190 sel_edge(U, NZ, Sel, NZ), 191 add_elem(X,NZ,NXZ), 192 set_equal(NXZ, NXZ1). 193/* old -> new */ 194sel_edge(V, NT, Sel, NXZ) :- 195 assign_sel_to_var(U,V,X,Y,Sel0), 196 var_edge(U, Y, NY), 197 sel_edge(U, NY, Sel0, NZ), 198 is_shared(U, NZ), 199 add_elem(X,NZ,NXZ), 200 sel_edge(U, NT, Sel, NZ), 201 not member(Y,NT), 202 disjoint_or_equal(NT, NXZ). /* Can be replaced by NT <> NZ or NT = {} */ 203/* old -> new */ 204sel_edge(V, NT, Sel, NXZ) :- 205 assign_sel_to_var(U,V,X,Y,Sel0), 206 var_edge(U, Y, NY), 207 sel_edge(U, NY, Sel0, NZ), 208 is_shared(U, NZ), 209 add_elem(X,NZ,NXZ), 210 sel_edge(U, NT, Sel, NZ), 211 Sel \== Sel0, 212 disjoint_or_equal(NT, NXZ). /* Can be replaced by NT <> NZ or NT = {} */ 213is_shared(V, NZ) :- 214 assign_sel_to_var(U,V,_X,_Y,_Sel0), 215 is_shared(U, NZ). 216is_shared(V, NXZ) :- 217 assign_sel_to_var(U,V,X,Y,Sel0), 218 is_shared(U,NZ), 219 var_edge(U, Y, NY), 220 sel_edge(U, NY, Sel0, NZ), 221 add_elem(X,NZ,NXZ). 222 223/* x.sel0 := y ------------------------------------------- */ 224 225var_edge(V, Z, NZ) :- 226 assign_var_to_sel(U,V,_X,_Sel0,_Y), 227 var_edge(U, Z, NZ). 228/* old edges */ 229sel_edge(V, NZ, Sel, NT) :- 230 assign_var_to_sel(U,V,_X,_Sel0,_Y), 231 sel_edge(U, NZ, Sel, NT). 232/* new edges */ 233sel_edge(V, NX, Sel0, NY) :- 234 assign_var_to_sel(U,V,X,Sel0,Y), 235 var_edge(U, X, NX), 236 var_edge(U, Y, NY), 237 disjoint_or_equal(NX, NY). 238is_shared(V, NZ) :- 239 assign_var_to_sel(U,V,_X,_Sel0,_Y), 240 is_shared(U, NZ). 241is_shared(V, NY) :- 242 assign_var_to_sel(U,V,_X,_Sel0,Y), 243 var_edge(U, Y, NY), 244 sel_edge(U, _, _, NY). 245 246