| 1 | % (c) 2016-2024 Lehrstuhl fuer Softwaretechnik und Programmiersprachen, | |
| 2 | % Heinrich Heine Universitaet Duesseldorf | |
| 3 | % This software is licenced under EPL 1.0 (http://www.eclipse.org/org/documents/epl-v10.html) | |
| 4 | ||
| 5 | :- module(b_operation_cache, [ %project_in_state/6, | |
| 6 | %operation_computed/4, | |
| 7 | compute_operation_on_expanded_store_cache/6, | |
| 8 | check_invariant_violated_cache/2, | |
| 9 | print_op_cache_profile/0, | |
| 10 | get_op_cache_stats/1, | |
| 11 | reset_b_operation_cache_with_statistics/0, | |
| 12 | tcltk_op_cache_stats/1 | |
| 13 | ]). | |
| 14 | ||
| 15 | ||
| 16 | :- use_module(probsrc(module_information)). | |
| 17 | :- module_info(group,animator). | |
| 18 | :- module_info(description,'This module caches B operation results on projected states. Used when preference try_operation_reuse different from false'). | |
| 19 | ||
| 20 | % TO DO: | |
| 21 | % provide predecessor ID and operation to know which values are unchanged? -> reuse hash; know which ops are definitely disabled? (cf pge) | |
| 22 | % Note: operation caching works better with COMPRESSION TRUE, as this way the values are pre-hashed. A simpler hash function is then used. | |
| 23 | % Note: if we change the MAX_OPERATIONS preference, this will have no effect on already cached operations | |
| 24 | % TODO: we could invalidate operation cache upon such a change; storing the value for each node is probably overkill | |
| 25 | ||
| 26 | :- use_module(probsrc(self_check)). | |
| 27 | :- use_module(extension('counter/counter')). % op_cache_id,... counter | |
| 28 | :- use_module(probsrc(succeed_max),[succeed_max_call_id/3, reset_max_reached/1, max_reached/1, assert_max_reached/1]). | |
| 29 | :- use_module(probsrc(eventhandling),[register_event_listener/3]). | |
| 30 | :- use_module(probsrc(error_manager)). | |
| 31 | :- use_module(probsrc(debug),[debug_println/2]). | |
| 32 | :- use_module(probsrc(performance_messages),[perfmessage/2]). | |
| 33 | :- use_module(library(ordsets), [ord_subtract/3]). | |
| 34 | :- use_module(probsrc(tools),[retract_with_statistics/2]). | |
| 35 | ||
| 36 | b_operation_cache_startup :- % call once at startup to ensure all counters exist | |
| 37 | counter_init, | |
| 38 | new_counter(op_cache_id), | |
| 39 | new_counter(inv_cache_nr), | |
| 40 | new_counter(op_cached_failures), | |
| 41 | new_counter(op_cached_successes), | |
| 42 | new_counter(inv_cached_successes), | |
| 43 | new_counter(op_cached_timeouts). | |
| 44 | ||
| 45 | ||
| 46 | :- register_event_listener(startup_prob,b_operation_cache_startup, | |
| 47 | 'Initialise Statespace Counters.'). | |
| 48 | :- register_event_listener(reset_specification,reset_b_operation_cache, | |
| 49 | 'Reset Operation Cache.'). | |
| 50 | :- register_event_listener(clear_specification,reset_b_operation_cache, % necessary? as reset occurs before? | |
| 51 | 'Reset Operation Cache.'). | |
| 52 | :- register_event_listener(change_of_animation_mode,reset_b_operation_cache, | |
| 53 | 'Reset Operation Cache.'). | |
| 54 | % TO DO: also reset if maxNrOfEnablingsPerOperation changed ? | |
| 55 | ||
| 56 | ||
| 57 | :- dynamic operation_read_projection_cache/5, operation_read_constants/2, operation_guard_read_info/3. | |
| 58 | reset_b_operation_cache :- | |
| 59 | retractall(operation_read_projection_cache(_,_,_,_,_)), | |
| 60 | retractall(operation_read_constants(_,_)), | |
| 61 | retractall(operation_guard_read_info(_,_,_)), | |
| 62 | retractall(operation_computed(_,_,_,_,_)), | |
| 63 | retractall(operation_cached_results(_,_,_,_)), | |
| 64 | retractall(operation_cached_max_reached(_,_)), | |
| 65 | retractall(operation_cached_time_out(_,_)), | |
| 66 | retractall(op_guard_fails(_,_,_)), | |
| 67 | reset_counter(op_cache_id), | |
| 68 | reset_counter(inv_cache_nr), | |
| 69 | reset_counter(op_cached_failures), | |
| 70 | reset_counter(op_cached_successes), | |
| 71 | reset_counter(inv_cached_successes). | |
| 72 | ||
| 73 | ||
| 74 | reset_b_operation_cache_with_statistics :- | |
| 75 | retract_with_statistics(b_operation_cache, | |
| 76 | [operation_read_projection_cache(_,_,_,_,_), | |
| 77 | operation_read_constants(_,_),operation_guard_read_info(_,_,_), | |
| 78 | operation_computed(_,_,_,_,_), operation_cached_results(_,_,_,_), | |
| 79 | operation_cached_max_reached(_,_), | |
| 80 | operation_cached_time_out(_,_), | |
| 81 | op_guard_fails(_,_,_) | |
| 82 | ] | |
| 83 | ), | |
| 84 | reset_b_operation_cache. | |
| 85 | ||
| 86 | ||
| 87 | % ------------------------------------------------- | |
| 88 | ||
| 89 | ||
| 90 | % project the in-state for an operation onto the relevant variables | |
| 91 | project_in_state(VarsInState,OpName,ProjectedInState) :- | |
| 92 | get_opname_key(OpName,OpNameKey), | |
| 93 | project_in_state_for_opname_key(VarsInState,OpNameKey,ProjectedInState). | |
| 94 | ||
| 95 | :- use_module(probsrc(bmachine),[b_is_constant/1]). | |
| 96 | :- use_module(library(lists),[exclude/3, include/3]). | |
| 97 | project_in_state_for_opname_key(InState,OpNameKey,ProjectedInState) :- | |
| 98 | get_operation_read_projection_infos(OpNameKey,_,InState,ProjVars,_,_), | |
| 99 | (re_project_state(ProjVars,InState,Res) -> ProjectedInState=Res | |
| 100 | ; add_internal_error('Re-Projection failed: ',re_project_state(ProjVars,InState,_)), | |
| 101 | ProjectedInState = InState). | |
| 102 | ||
| 103 | :- use_module(probsrc(specfile),[csp_with_bz_mode/0]). | |
| 104 | :- use_module(probsrc(b_read_write_info),[b_get_operation_read_guard_vars/4]). | |
| 105 | :- use_module(probsrc(bmachine),[b_definition_prefixed/5]). | |
| 106 | ||
| 107 | ||
| 108 | % get infos about cached operations (and compute the first time info requested for an operation) | |
| 109 | get_operation_read_projection_infos(OpNameKey,OpName,_,ProjVars,IsReadingCsts,AdditionalOutVars) :- | |
| 110 | operation_read_projection_cache(OpNameKey,OpName,ProjVars,IsReadingCsts,AdditionalOutVars),!, | |
| 111 | ProjVars \= no_caching. | |
| 112 | get_operation_read_projection_infos(OpNameKey,OpName,_,_,_,_) :- atom(OpName), | |
| 113 | b_definition_prefixed(_, 'OPERATION_REUSE_OFF_', OpName, _DefName,_), | |
| 114 | !, | |
| 115 | format('Ignoring operation ~w for reuse~n',[OpName]), | |
| 116 | assertz(operation_read_projection_cache(OpNameKey,OpName,no_caching,no_caching,[])), | |
| 117 | fail. | |
| 118 | get_operation_read_projection_infos(OpNameKey,OpName,InState,ProjVarsInOrder,IsReadingCsts,AdditionalOutVars) :- | |
| 119 | api_get_operation_read_write_info(OpName,ReadVariables,ReadConstants,WrittenVariables), | |
| 120 | (ReadConstants=[] -> IsReadingCsts=false ; IsReadingCsts=true), | |
| 121 | debug_println(19,operation_reads_vars_consts(OpName,ReadVariables,ReadConstants)), | |
| 122 | (project_state_onto_vars(InState,ReadVariables,ProjVarsInOrder,_RelevantState,0,NrDeleted) | |
| 123 | -> % TO DO: if we have constants in the state which are deterministic anyway, then they should not count | |
| 124 | % TO DO: statically pre-compute which operations are worthwhile for this treatment | |
| 125 | ((NrDeleted>0 % we project away at least one variable and thus hope to cache operation results | |
| 126 | ; csp_with_bz_mode) % in CSP||B mode, the same operation may be called with different CSP controllers | |
| 127 | -> ord_subtract(WrittenVariables,ReadVariables,AdditionalOutVars), % vars written but not read | |
| 128 | assertz(operation_read_projection_cache(OpNameKey,OpName,ProjVarsInOrder,IsReadingCsts,AdditionalOutVars)), | |
| 129 | assertz(operation_read_constants(OpNameKey,ReadConstants)), | |
| 130 | % ,print(proj(OpName,ProjVarsInOrder,AdditionalOutVars)),nl, | |
| 131 | (get_preference(try_operation_reuse,full), | |
| 132 | b_get_operation_read_guard_vars(OpName,true,ReadVarsInGuard,precise), | |
| 133 | exclude(member_ord(ReadVarsInGuard),ProjVarsInOrder,IrrelevantVars), | |
| 134 | % TO DO: analyse if projection really useful | |
| 135 | IrrelevantVars \= [] | |
| 136 | -> include(member_ord(ReadVarsInGuard),ProjVarsInOrder,ReadVarsInGuard), | |
| 137 | debug_println(19,guard_reads_subset_of_vars(OpName,OpNameKey,ReadVarsInGuard,IrrelevantVars)), | |
| 138 | assertz(operation_guard_read_info(OpNameKey,ReadVarsInGuard,IrrelevantVars)) | |
| 139 | ; true) | |
| 140 | ; assertz(operation_read_projection_cache(OpNameKey,OpName,no_caching,no_caching,[])), | |
| 141 | perfmessage('Not caching operation for reuse: ',OpName), | |
| 142 | fail | |
| 143 | ) | |
| 144 | ; add_internal_error('Projection failed for: ', project_state_onto_vars(InState,ReadVariables,_,_,0,_)), | |
| 145 | assertz(operation_read_projection_cache(OpNameKey,OpName,no_caching,no_caching,[])), | |
| 146 | fail | |
| 147 | ). | |
| 148 | %TODO: also compute precise guard b_get_operation_read_guard_vars(Operation,JustVariables,VarsResult,VarsPrecise) if possible and if read vars in guard << ReadVariables also store this | |
| 149 | % if operation call fails -> store only precise guard | |
| 150 | ||
| 151 | % ------------------------------- | |
| 152 | ||
| 153 | % API to abstract operations so that we can use caching also for invariants, maybe later assertions, ... | |
| 154 | ||
| 155 | % get atomic key to store operation info | |
| 156 | get_opname_key(Name,Res) :- var(Name),!, | |
| 157 | add_internal_error('Variable opname: ',get_opname_key(Name,Res)), Res=Name. | |
| 158 | get_opname_key(check_invariant_violated(Nr),Key) :- !, Key=Nr. | |
| 159 | get_opname_key(Name,Name). | |
| 160 | ||
| 161 | api_get_operation_read_write_info(OpName,ReadVariables,ReadConstants,WrittenVariables) :- | |
| 162 | api_get_op_rw_aux(OpName,ReadIds,WrittenVariables), | |
| 163 | exclude(b_is_constant,ReadIds,ReadVariables), | |
| 164 | include(b_is_constant,ReadIds,ReadConstants). | |
| 165 | :- use_module(probsrc(bmachine),[b_nth1_invariant/3,b_get_operation_normalized_read_write_info/3]). | |
| 166 | api_get_op_rw_aux(check_invariant_violated(Nr),UsedIds,Written) :- !, Written=[], | |
| 167 | b_nth1_invariant(Nr,_,UsedIds). | |
| 168 | api_get_op_rw_aux(OpName,ReadVariables,WrittenVariables) :- | |
| 169 | b_get_operation_normalized_read_write_info(OpName,ReadVariables,WrittenVariables). | |
| 170 | ||
| 171 | ||
| 172 | :- use_module(probsrc(b_interpreter),[b_execute_top_level_operation_update/5]). | |
| 173 | ||
| 174 | % we use a trick using a mutable to detect when a time_out or exception has been thrown | |
| 175 | % during caching; we could have used assert/retract or bb_put/bb_get instead | |
| 176 | ||
| 177 | api_compute_operation_update_max(NewID,OpName,Operation,ProjInOutState,NewState,PathInfo,MaxForCall) :- | |
| 178 | create_mutable(still_computing,Done), | |
| 179 | %tools:start_ms_timer(Timer), | |
| 180 | call_cleanup( | |
| 181 | com_op_update_max(NewID,OpName,Operation,ProjInOutState,NewState,PathInfo,MaxForCall,Done), | |
| 182 | (get_mutable(still_computing,Done) | |
| 183 | -> format('Timeout, exception or virtual timeout occured during caching for ~w (cache id ~w)~n',[OpName,NewID]), | |
| 184 | % also happens during -execute due to cut!, hence we now disable preference in -execute | |
| 185 | % stop_ms_timer_with_msg(Timer,'Runtime for computing'), | |
| 186 | inc_counter(op_cached_timeouts), | |
| 187 | register_op_cache_time_out(NewID,OpName) | |
| 188 | ; true | |
| 189 | )), | |
| 190 | get_mutable(DVal,Done), DVal \= finished. % fail if we are Done; | |
| 191 | ||
| 192 | % we could do this: but we don't know if an exception, timeout or virtual time_out occurred | |
| 193 | register_op_cache_time_out(ID,OpName) :- | |
| 194 | inc_counter(op_cached_timeouts), | |
| 195 | assertz(operation_cached_time_out(ID,OpName)). | |
| 196 | % as an alternative this removes the cached results: | |
| 197 | %invalidate_operation_cache(ID,OpName) :- | |
| 198 | % retractall(operation_cached_results(ID,_Operation,_,_)), | |
| 199 | % retractall(operation_computed(_,OpName,_,_,ID)). % can be expensive | |
| 200 | ||
| 201 | ||
| 202 | ||
| 203 | com_op_update_max(_,check_invariant_violated(Nr),Operation,ProjState,NewState,PathInfo,_,Done) :- !, | |
| 204 | NewState =[], PathInfo=invariant, Operation=Nr, % values not used anyway for invariants | |
| 205 | %print(check_invariant(Nr)),nl, bmachine:b_nth1_invariant(Nr,Inv,_UsedIds), translate:print_bexpr(Inv),nl, | |
| 206 | (b_interpreter:check_nth1_invariant(Nr,ProjState ) | |
| 207 | -> update_mutable(finished,Done) % will lead to failure above; we store only violations | |
| 208 | ; % invariant violation found | |
| 209 | update_mutable(last_sol_found,Done) | |
| 210 | ). | |
| 211 | com_op_update_max(_,OpName,Operation,ProjInOutState,NewState,PathInfo,MaxForCall,_) :- | |
| 212 | % for CSP||B: clear out any parameters; otherwise we also need to hash the parameters | |
| 213 | reset_max_reached(OpName), | |
| 214 | succeed_max_call_id(OpName, | |
| 215 | b_execute_top_level_operation_update(OpName,Operation,ProjInOutState,NewState,PathInfo), | |
| 216 | MaxForCall). | |
| 217 | % TO DO: normalise_store out state values, to avoid re-normalising when storing updates | |
| 218 | com_op_update_max(NewID,OpName,_,_,_,_,_,Done) :- | |
| 219 | (NewID \= uncached, | |
| 220 | max_reached(OpName) | |
| 221 | -> assertz(operation_cached_max_reached(NewID,OpName)) % store that we reached max. nr of transitions for this node | |
| 222 | ; true %format('No Timeout or virtual timeout occurred during caching for ~w leading to ~w~n',[OpName,NewID]) | |
| 223 | ), | |
| 224 | update_mutable(finished,Done). | |
| 225 | ||
| 226 | ||
| 227 | ||
| 228 | % entry point to cache invariant checking | |
| 229 | check_invariant_violated_cache(Nr,State) :- | |
| 230 | %get_store_and_info(State,FullStore,Infos), | |
| 231 | compute_operation_on_expanded_store_cache(check_invariant_violated(Nr),_,State,_,_,-1). | |
| 232 | ||
| 233 | :- use_module(probsrc(specfile),[expand_const_and_vars_to_full_store/2]). | |
| 234 | %get_store_and_info(expanded_const_and_vars(_ConstID,_Vars,E,Info),FullStore,Info) :- !, FullStore=E. | |
| 235 | %get_store_and_info(expanded_vars(E,Info),FullStore,Info) :- !, FullStore=E. | |
| 236 | %get_store_and_info(Store,FullStore,[]) :- expand_const_and_vars_to_full_store(Store,FullStore). | |
| 237 | ||
| 238 | % ------------------------------- | |
| 239 | ||
| 240 | ||
| 241 | % check if caching is worthwhile for this operation | |
| 242 | %worthwhile_to_cache(OpName) :- | |
| 243 | % get_read_write_info(OpName,ReadVariables,WrittenVariables), | |
| 244 | % length(ReadVariables,NrRV), | |
| 245 | % bmachine:b_machine_statistics(variables,NrVars), | |
| 246 | % bmachine:b_machine_statistics(constants,NrConstants), | |
| 247 | % Perc is (NrRV*100) // (NrVars+NrConstants), | |
| 248 | % length(WrittenVariables,NrWV), | |
| 249 | % format('Analyzing ~w, ~w %, read: ~w, written: ~w, tot vars: ~w, tot cst: ~w~n (read: ~w)~n',[OpName,Perc,NrRV,NrWV,NrVars,NrConstants,ReadVariables]), | |
| 250 | % Perc < 95. % maybe provide as preference | |
| 251 | ||
| 252 | :- use_module(library(ordsets),[ord_member/2]). | |
| 253 | %is_read(ReadVariables,bind(Var,_)) :- ord_member(Var,ReadVariables). | |
| 254 | member_ord(List,X) :- ord_member(X,List). % for maplist, exclude,... | |
| 255 | ||
| 256 | % ------------------------------- | |
| 257 | ||
| 258 | % a variation of split_list which also returns a list of predicate results | |
| 259 | % with re_project_state(L,ProjVarsInOrder,A) : we can split another list using the same pattern | |
| 260 | ||
| 261 | :- assert_must_succeed((b_operation_cache:project_state_onto_vars([bind(x,1),bind(y,2),bind(b,3)],[b,y], | |
| 262 | ProjVars,ProjState,0,NrDel), | |
| 263 | ProjVars == [y,b], ProjState == [bind(y,2),bind(b,3)], NrDel==1)). | |
| 264 | ||
| 265 | project_state_onto_vars([],_,[],[],Acc,Acc). | |
| 266 | project_state_onto_vars([Elem|Rest],ReadVariables,ProjVars,ProjState,NrDelAcc,NrDel) :- | |
| 267 | Elem = bind(Var,_), | |
| 268 | (ord_member(Var,ReadVariables) % TO DO: we could improve performance by sorting Elements | |
| 269 | -> ProjVars=[Var|PT], ProjState=[Elem|AR], ND1=NrDelAcc | |
| 270 | ; ProjVars=PT, ProjState=AR, ND1 is NrDelAcc+1), | |
| 271 | project_state_onto_vars(Rest,ReadVariables,PT,AR,ND1,NrDel). | |
| 272 | ||
| 273 | ||
| 274 | % ------------------------------- | |
| 275 | ||
| 276 | :- assert_must_succeed((b_operation_cache:re_project_state([y,b],[bind(x,1),bind(y,2),bind(b,3)],Res), | |
| 277 | Res == [bind(y,2),bind(b,3)])). | |
| 278 | ||
| 279 | % project state(VarsInOrder,State,ProjectedState) | |
| 280 | % faster than project_state_onto_vars | |
| 281 | re_project_state([],_,[]). | |
| 282 | re_project_state([VarToProject|PT],[Elem|Rest],A) :- | |
| 283 | arg(1,Elem,Var), %Elem = bind(Var,_), | |
| 284 | (VarToProject==Var | |
| 285 | -> A=[Elem|AR],re_project_state(PT,Rest,AR) | |
| 286 | ; re_project_state2(VarToProject,PT,Rest,A)). | |
| 287 | ||
| 288 | re_project_state2(VarToProject,PT,[Elem|Rest],A) :- | |
| 289 | arg(1,Elem,Var), %Elem = bind(Var,_), | |
| 290 | (VarToProject==Var | |
| 291 | -> A=[Elem|AR],re_project_state(PT,Rest,AR) | |
| 292 | ; re_project_state2(VarToProject,PT,Rest,A)). | |
| 293 | ||
| 294 | % ----------------------------- | |
| 295 | ||
| 296 | % Two utilities to optionally generate lemma facts for fast projection | |
| 297 | % Does not seem to be worth it | |
| 298 | ||
| 299 | % abstract away values, can be used to generate pre-compiled facts | |
| 300 | %abstract_state([],[]). | |
| 301 | %abstract_state([bind(Var,_)|T],[bind(Var,_)|AT]) :- abstract_state(T,AT). | |
| 302 | ||
| 303 | % abstract away unused bindings, can be used to generate pre-compiled facts | |
| 304 | %clear_unused_bindings([],_,_) :- !. | |
| 305 | %clear_unused_bindings([VarToProject|PT],[bind(Var,V)|T],[bind(Var,V)|RT]) :- | |
| 306 | % % we could clear out Variable name Var; but this creates a danger of successfully matching an erroneous state | |
| 307 | % VarToProject==Var,!, | |
| 308 | % clear_unused_bindings(PT,T,RT). | |
| 309 | %clear_unused_bindings(Vars,[_|T],[_|RT]) :- % leave slot in result as fresh var | |
| 310 | % clear_unused_bindings(Vars,T,RT). | |
| 311 | ||
| 312 | % ------------------------------- | |
| 313 | ||
| 314 | :- use_module(probsrc(hashing)). | |
| 315 | :- use_module(probsrc(state_packing)). | |
| 316 | ||
| 317 | :- dynamic operation_computed/5, operation_cached_results/4, | |
| 318 | operation_cached_max_reached/2, operation_cached_time_out/2, | |
| 319 | op_guard_fails/3. | |
| 320 | ||
| 321 | % return Hash and check if operation computed | |
| 322 | % TO DO: do not hash constants if single value exists ? | |
| 323 | check_if_operation_was_computed(OpName,ConstID,State,Skel,Infos,PackedValList,IsReadingCsts, | |
| 324 | HashConstID,Hash,Res) :- | |
| 325 | (Infos = [packed_state/PS|_] | |
| 326 | -> get_packed_vars(PS,OpName,PackedState), | |
| 327 | remove_bind_skeleton(PackedState,Skel,PackedValList) | |
| 328 | % packing already performed in prepare_state_for_specfile_trans | |
| 329 | ; write(no_packed_state_info(OpName,ConstID)),nl, % shouldn't happen hopefully | |
| 330 | project_in_state(State,OpName,ProjectedInState), % State contains just variables | |
| 331 | pack_bind_list(ProjectedInState,Skel,PackedValList) | |
| 332 | ), | |
| 333 | (IsReadingCsts = false -> HashConstID=root ; HashConstID=ConstID), | |
| 334 | op_hash(OpName,HashConstID,PackedValList,Hash), | |
| 335 | (operation_computed(Hash,OpName,HashConstID,PackedValList,ID) | |
| 336 | -> Res = ID | |
| 337 | ; % operation_guard_read_info(OpKey,GuardVars,_), re_project_state(GuardVars,Skel,PackedValList,GuardPackedVals) | |
| 338 | % op_hash(OpName,HashConstID,GuardPackedVals,GuardHash), op_guard_fails(GuardHash,OpName,GuardPackedVals,ID) -> true | |
| 339 | Res= false). | |
| 340 | ||
| 341 | % project a state or packed value list onto the variables relevant for the guard (if it is a subset) | |
| 342 | project_onto_guard(OpName,OpKey,HashConstID,Skel,PackedValList,GuardPackedVals,GuardHash) :- | |
| 343 | operation_guard_read_info(OpKey,_,IgnoredVars), | |
| 344 | remove_ignored_vars(IgnoredVars,Skel,PackedValList,GuardPackedVals), | |
| 345 | op_hash(OpName,HashConstID,GuardPackedVals,GuardHash). | |
| 346 | ||
| 347 | ||
| 348 | % remove_ignored_vars(VarsToIgnore,SkeletonList,ValueList,Result) | |
| 349 | remove_ignored_vars([],_,PackedVals,Res) :- Res=PackedVals. | |
| 350 | remove_ignored_vars([ID|T],[ID|ST],[_|PackedVals],GuardPackedVals) :- !, | |
| 351 | remove_ignored_vars(T,ST,PackedVals,GuardPackedVals). | |
| 352 | remove_ignored_vars(Ignored,[_|ST],[PV|PackedVals],[PV|GuardPackedVals]) :- | |
| 353 | remove_ignored_vars(Ignored,ST,PackedVals,GuardPackedVals). | |
| 354 | ||
| 355 | get_packed_vars(const_and_vars(_,Vars),OpName,PackedVars) :- !, project_in_state(Vars,OpName,PackedVars). | |
| 356 | get_packed_vars(PS,OpName,PackedVars) :- !, project_in_state(PS,OpName,PackedVars). | |
| 357 | :- use_module(library(terms),[term_hash/3]). | |
| 358 | :- use_module(probsrc(hashing),[my_term_hash/2]). | |
| 359 | ||
| 360 | op_hash(OpName,HashConstID,PackedValList,Hash) :- get_preference(use_state_packing,false),!, | |
| 361 | my_term_hash((OpName,HashConstID,PackedValList),Hash). % will user super_hash | |
| 362 | op_hash(OpName,HashConstID,PackedValList,Hash) :- | |
| 363 | % we use state packing and thus replace AVL sets by identifiers, ...: a simpler hash suffices, but we get collisions for Train1_Lukas_POR (which do not seem to matter); we get an improvement for ifm18/Ref5_Switch_mch.eventb | |
| 364 | term_hash((OpName,HashConstID,PackedValList), | |
| 365 | [range(smallint),algorithm(sdbm),depth(infinite),if_var(ignore)], % djb2 | |
| 366 | Hash). | |
| 367 | ||
| 368 | ||
| 369 | % remove bind/2 wrappers and variable name for faster hashing | |
| 370 | remove_bind_skeleton([],[],R) :- !, R=[]. | |
| 371 | remove_bind_skeleton([bind(Var,Val)|T],[Var|VT],[Val|RT]) :- !, | |
| 372 | remove_bind_skeleton(T,VT,RT). | |
| 373 | remove_bind_skeleton(L,V,R) :- add_internal_error('Illegal store: ',remove_bind_skeleton(L,V,R)), R=L. | |
| 374 | ||
| 375 | % we could also peel a few infos not useful for hashing: | |
| 376 | %peel_val('$stored_avl_packed'(Nr),Nr). | |
| 377 | %peel_val('$avl_bv'(Nr,_),Nr). % correct because if we use a bit_vector we will never also use stored_avl_packed for the same type | |
| 378 | ||
| 379 | ||
| 380 | get_new_operation_computed_id(OpName,ConstID,PackedValList,Hash,ID) :- | |
| 381 | inc_counter(op_cache_id,ID), | |
| 382 | (OpName=check_invariant_violated(_) -> inc_counter(inv_cache_nr,_) ; true), | |
| 383 | assertz(operation_computed(Hash,OpName,ConstID,PackedValList,ID)). | |
| 384 | % To reduce memory consumption we could use the following clause: | |
| 385 | % can be useful if there are many operations with a large number of projected variables | |
| 386 | % but does lead to noticable slowdown when looking up operations | |
| 387 | %get_new_operation_computed_id(OpName,ConstID,_PackedValList,Hash,[_,state_id/ReferenceStateID],ID) :- !, | |
| 388 | % inc_counter(op_cache_id,ID), | |
| 389 | % assertz(operation_computed(Hash,OpName,ConstID,ReferenceStateID,ID)). % storing reference ID preserves memory | |
| 390 | % when looking up operation_was_computed we would need to do something like: | |
| 391 | % state_space:packed_visited_expression(StoredState,PS), | |
| 392 | % get_packed_b_state_with_uncompressed_lists(PS,PUS), | |
| 393 | % get_state_infos(PUS,ConstID,PackedList,_,_), | |
| 394 | % project_in_state(PackedList,OpName,ProjectedStoredState), | |
| 395 | % remove_bind_skeleton(ProjectedStoredState,Skel,ProjectedValList), | |
| 396 | % ProjectedValList = PackedValList | |
| 397 | ||
| 398 | ||
| 399 | :- use_module(probsrc(runtime_profiler),[profile_failure_driven_loop/1]). | |
| 400 | % this is used when get_preference(try_operation_reuse,true/full) | |
| 401 | % it is only called for operations, not for setup_constants or initalise_machine | |
| 402 | ||
| 403 | % treat expanded_const_and_vars(ConstID,Vars,FullStore,Infos) | |
| 404 | ||
| 405 | get_state_infos(expanded_const_and_vars(ID,Vars,FullStore,I),ConstID,Vars,FullStore,Infos) :- !,ConstID=ID,Infos=I. | |
| 406 | get_state_infos(expanded_vars(V,I),ConstID,Vars,FullStore,Infos) :- !, ConstID=root,Vars=V,FullStore=V,Infos=I. | |
| 407 | get_state_infos(const_and_vars(ConstID,Vars),ConstID,Vars,FullStore,Infos) :- !, | |
| 408 | add_warning(get_state_infos,'State not prepared for caching: ',const_and_vars(ConstID,Vars)), | |
| 409 | Infos=[], | |
| 410 | expand_const_and_vars_to_full_store(const_and_vars(ConstID,Vars),FullStore). | |
| 411 | get_state_infos(csp_and_b(_,State),ConstID,Vars,FullStore,Infos) :- !, | |
| 412 | get_state_infos(State,ConstID,Vars,FullStore,Infos). | |
| 413 | get_state_infos(Vars,unknown,Vars,Vars,[]). | |
| 414 | ||
| 415 | % InState is either already an expanded list or expanded_const_and_vars, expanded_vars | |
| 416 | compute_operation_on_expanded_store_cache(OpName,Operation,InState,NewState,PathInfo,MaxForCall) :- | |
| 417 | get_state_infos(InState,ConstID,Vars,FullStore,Infos), % extract infos from the store | |
| 418 | % TO DO: check if state_id in Infos and if OpName in equivalence class with same proj. vars | |
| 419 | get_opname_key(OpName,OpNameKey), | |
| 420 | get_operation_read_projection_infos(OpNameKey,OpName,Vars,ProjVarsInOrder,IsReadingCsts,AdditionalOutVars), | |
| 421 | !, | |
| 422 | % tools_printing:print_term_summary(proj(OpName,ConstID,ProjInState,FullStore)),nl, | |
| 423 | check_if_operation_was_computed(OpName,ConstID,Vars,ProjVarsInOrder,Infos,PackedValList,IsReadingCsts, | |
| 424 | HashConstID,Hash,ID), | |
| 425 | (ID \= false | |
| 426 | -> % we can reuse the stored operation effect | |
| 427 | %print('+'), | |
| 428 | %hit_profiler:add_hit(operation_reused,OpName), | |
| 429 | (inv_op_name(OpName) -> inc_counter(inv_cached_successes) | |
| 430 | ; inc_counter(op_cached_successes)), | |
| 431 | (operation_cached_results(ID,Operation,PackedNewState,PathInfo), | |
| 432 | unpack_values(PackedNewState,NewState) | |
| 433 | ; | |
| 434 | operation_cached_max_reached(ID,OpName), % we did not compute all operations | |
| 435 | assert_max_reached(OpName), | |
| 436 | fail | |
| 437 | ; operation_cached_time_out(ID,OpName), | |
| 438 | format('Rethrowing cached time_out for ~w and cache id ~w~n',[OpName,ID]), | |
| 439 | throw(time_out) | |
| 440 | ) | |
| 441 | ; % we have not computed solutions for this operation for this projected state | |
| 442 | (project_onto_guard(OpName,OpNameKey,HashConstID,ProjVarsInOrder,PackedValList,GuardPackedVals,GuardHash) | |
| 443 | -> true | |
| 444 | ; GuardPackedVals = none), | |
| 445 | (nonvar(GuardHash), | |
| 446 | op_guard_fails(GuardHash,OpName,GuardPackedVals) | |
| 447 | -> % we did already compute this operation for this projected state and it failed | |
| 448 | inc_counter(op_cached_failures), | |
| 449 | fail % the guard is guaranteed to fail | |
| 450 | ; % we have not yet computed this operation; compute it and store solutions as we go | |
| 451 | get_new_operation_computed_id(OpName,HashConstID,PackedValList,Hash,NewID), | |
| 452 | %print('-'), | |
| 453 | %hit_profiler:add_hit(operation_cache_computation,OpName), | |
| 454 | (IsReadingCsts=false | |
| 455 | -> % TO DO: check if this projection is worthwhile | |
| 456 | project_in_state_for_opname_key(Vars,OpNameKey,ProjInState), | |
| 457 | % Note: if no packed_state this projection was already performed in check_if_operation_was_computed | |
| 458 | add_new_vars(AdditionalOutVars,ProjInState,ProjInOutState) | |
| 459 | ; ProjInOutState = FullStore % use full store with constants | |
| 460 | ), | |
| 461 | profile_failure_driven_loop(OpName), | |
| 462 | if(api_compute_operation_update_max(NewID,OpName,Operation,ProjInOutState,NewState,PathInfo,MaxForCall), | |
| 463 | (% Normalise here or in update_max | |
| 464 | pack_values(NewState,PackedNewState), | |
| 465 | (PathInfo=invariant -> StoredPathInfo=Hash | |
| 466 | ; filter_transition_path_info(PathInfo,StoredPathInfo)), | |
| 467 | assertz(operation_cached_results(NewID,Operation,PackedNewState,StoredPathInfo)) | |
| 468 | ), | |
| 469 | (nonvar(GuardHash), | |
| 470 | %print(op_guard_fails(GuardHash,OpName,GuardPackedVals)),nl, | |
| 471 | assertz(op_guard_fails(GuardHash,OpName,GuardPackedVals)), | |
| 472 | fail | |
| 473 | ) | |
| 474 | ) | |
| 475 | ) | |
| 476 | % TO DO: if we have no successors for ID and if the operation reads less IDs in the guard | |
| 477 | % we can replace remaining identifier values by a variable | |
| 478 | ). | |
| 479 | compute_operation_on_expanded_store_cache(OpName,Operation,InState,NewState,PathInfo,MaxForCall) :- | |
| 480 | %hit_profiler:add_hit(operation_not_cached,OpName), | |
| 481 | % operation is not cached | |
| 482 | get_state_infos(InState,_,_,FullStore,_), | |
| 483 | api_compute_operation_update_max(uncached,OpName,Operation,FullStore,NewState,PathInfo,MaxForCall). | |
| 484 | ||
| 485 | % add written vars which are not read virtually to state to avoid error messages in store_intermediate_updates: | |
| 486 | add_new_vars([],S,S). | |
| 487 | add_new_vars([WrittenVar|T],State,[bind(WrittenVar,term(undefined))|ST]) :- | |
| 488 | add_new_vars(T,State,ST). | |
| 489 | ||
| 490 | :- use_module(probsrc(state_space),[keep_transition_info/1]). | |
| 491 | filter_transition_path_info([],R) :- !, R=[]. | |
| 492 | filter_transition_path_info([H|T],Res) :- !, | |
| 493 | (keep_transition_info(H) -> Res = [H|RT] | |
| 494 | ; Res=RT), % by default we filter out possibly large path infos (in particular for Event-B) | |
| 495 | filter_transition_path_info(T,RT). | |
| 496 | filter_transition_path_info(H,Res) :- | |
| 497 | (keep_transition_info(H) -> Res = H ; Res=[]). | |
| 498 | ||
| 499 | ||
| 500 | invariant_op_key(OpKey,InvNr) :- operation_read_projection_cache(OpKey,check_invariant_violated(InvNr),_,_,_). | |
| 501 | ||
| 502 | :- use_module(probsrc(bmachine),[b_nth1_invariant/3]). | |
| 503 | print_violated_invariants :- | |
| 504 | operation_cached_results(ID,Nr,[],Hash),number(Nr), | |
| 505 | b_nth1_invariant(Nr,Invariant,_UsedIds), | |
| 506 | format('Invariant ~w violated (op-cache-id ~w)~n ',[Nr,ID]), | |
| 507 | translate:print_bexpr(Invariant),nl, | |
| 508 | % now try and recover state where it was violated: | |
| 509 | operation_computed(Hash,OpName,ConstID,PackedValList,ID), | |
| 510 | operation_read_projection_cache(_,OpName,Skel,_,_), | |
| 511 | unpack_bind_list(PackedValList,Skel,State), translate_bstate_limited(State,StateDesc), | |
| 512 | format(' in state (ConstID ~w) ~w~n',[ConstID,StateDesc]), | |
| 513 | fail. | |
| 514 | print_violated_invariants. | |
| 515 | ||
| 516 | % small utility code to analyze hash collisions: | |
| 517 | % b_operation_cache:ahc. | |
| 518 | :- public ahc/0. | |
| 519 | ahc :- operation_computed(Hash,OpName,ConstID,State,ID), | |
| 520 | operation_computed(Hash,OpName2,ConstID2,State2,ID2), | |
| 521 | (ConstID @> ConstID2 -> true ; ConstID=ConstID2, ID2 > ID), | |
| 522 | format('Hash collision: ~w~n ~w:~w:~w:~w~n ~w:~w:~w:~w~n~n', | |
| 523 | [Hash,OpName,ConstID,State,ID,OpName2,ConstID2,State2,ID2]), | |
| 524 | fail. | |
| 525 | ahc. | |
| 526 | ||
| 527 | :- use_module(probsrc(translate),[translate_bstate_limited/2, translate_event_with_limit/3]). | |
| 528 | :- use_module(probsrc(debug),[debug_mode/1]). | |
| 529 | :- use_module(probsrc(preferences),[get_preference/2]). | |
| 530 | :- use_module(probsrc(specfile),[get_operation_name/2]). | |
| 531 | get_op_name(Nr,check_invariant_violated(Nr)) :- number(Nr),!. | |
| 532 | get_op_name(Op,OpName) :- get_operation_name(Op,OpName). | |
| 533 | get_nr_next_state_calls(OpName,Nr) :- findall(1,operation_computed(_Hash,OpName,_,_,_ID),Ls), length(Ls,Nr). | |
| 534 | get_nr_cache_results(OpName,RNr) :- | |
| 535 | findall(1,(operation_cached_results(_ID,Op,_,_),get_op_name(Op,OpName)),Rs), length(Rs,RNr). | |
| 536 | :- use_module(probsrc(bmachine),[b_get_machine_variables/1]). | |
| 537 | % b_operation_cache:print_op_cache_profile | |
| 538 | ||
| 539 | check_if_op_cache_useful :- | |
| 540 | b_get_machine_variables(Var),length(Var,VLen), | |
| 541 | api_get_operation_read_write_info(OpName,ReadVariables,_ReadConstants,_WrittenVariables), | |
| 542 | length(ReadVariables,ReadLen), | |
| 543 | ReadLen < VLen, | |
| 544 | (inv_op_name(OpName) -> get_preference(use_po,false) ; true), | |
| 545 | format('Operation reuse potentially useful: ~w reads ~w/~w variables~n',[OpName,ReadLen,VLen]), | |
| 546 | fail. | |
| 547 | check_if_op_cache_useful. | |
| 548 | ||
| 549 | inv_op_name(check_invariant_violated(_)). | |
| 550 | ||
| 551 | print_op_cache_profile :- \+ operation_computed(_,_,_,_,_),!, % print nothing | |
| 552 | (get_preference(try_operation_reuse,false) -> format('OPERATION_REUSE preference not set to TRUE~n',[]) ; true), | |
| 553 | format('No operation cached~n',[]), | |
| 554 | check_if_op_cache_useful. | |
| 555 | print_op_cache_profile :- | |
| 556 | b_get_machine_variables(Var),length(Var,VLen), | |
| 557 | operation_read_projection_cache(OpKey,OpName,ProjVars,_,WV), (ProjVars = [] ; ProjVars = [_|_]), | |
| 558 | length(ProjVars,Len), | |
| 559 | operation_read_constants(OpKey,ReadConstants), | |
| 560 | (operation_guard_read_info(OpKey,_,IrrelevantVars) | |
| 561 | -> format('Operation ~w cached onto ~w/~w variables: ~w (not relevant for guard: ~w, only written: ~w, constants read: ~w)~n',[OpName,Len,VLen,ProjVars,IrrelevantVars,WV,ReadConstants]) | |
| 562 | ; format('Operation ~w cached onto ~w/~w variables: ~w (only written: ~w, constants read: ~w)~n',[OpName,Len,VLen,ProjVars,WV,ReadConstants]) | |
| 563 | ),fail. | |
| 564 | print_op_cache_profile :- findall(OpName,operation_read_projection_cache(_,OpName,no_caching,_,_),Ls), | |
| 565 | format('Operations not cached: ~w~n',[Ls]),fail. | |
| 566 | print_op_cache_profile :- operation_read_projection_cache(OpKey,OpName,ProjVars,_,_), ProjVars = [_|_], | |
| 567 | get_nr_next_state_calls(OpName,Nr), | |
| 568 | get_nr_cache_results(OpName,RNr), | |
| 569 | (inv_op_name(OpName) -> Results='violations' ; Results = 'results'), | |
| 570 | format('Next-state-calls for ~w: ~w (~w ~w)~n',[OpName,Nr,RNr,Results]), | |
| 571 | operation_guard_read_info(OpKey,RelVars,_), | |
| 572 | findall(1,op_guard_fails(_,OpName,_),Fails), length(Fails,NrFails), | |
| 573 | format(' projected-failures (on ~w): ~w~n',[RelVars,NrFails]), | |
| 574 | fail. | |
| 575 | print_op_cache_profile :- | |
| 576 | get_total_number_of_next_state_calls(Nr,InvNr), | |
| 577 | format('Total Number of Next-state-calls for Operations: ~w~n',[Nr]), | |
| 578 | get_counter(op_cached_failures,FailCalls), | |
| 579 | format(' - Reused guard failures: ~w~n',[FailCalls]), | |
| 580 | get_counter(op_cached_successes,SuccCalls), | |
| 581 | format(' - Reused successful operation call results: ~w~n',[SuccCalls]), | |
| 582 | format('Total Number of Invariant-check-calls: ~w~n',[InvNr]), | |
| 583 | get_counter(inv_cached_successes,SuccInvCalls), | |
| 584 | format(' - Reused invariant check results: ~w~n',[SuccInvCalls]), | |
| 585 | fail. | |
| 586 | print_op_cache_profile :- debug_mode(on), nl, | |
| 587 | operation_read_projection_cache(_,OpName,Skel,_,_), | |
| 588 | format('~n** Local Operation Cache Info for ~w ** (projected on ~w):~n',[OpName,Skel]), | |
| 589 | operation_computed(_Hash,OpName,ConstID,PackedValList,ID), | |
| 590 | (operation_cached_max_reached(ID,OpName) -> MaxR='(max reached, not all transitions computed)' | |
| 591 | ; MaxR=''), | |
| 592 | format('~nNode ID = ~w, Operation = ~w ~w~n',[ID,OpName,MaxR]), | |
| 593 | unpack_bind_list(PackedValList,Skel,State), translate_bstate_limited(State,NodeDesc), | |
| 594 | format(' projected state : (ConstID ~w) ~w~n',[ConstID,NodeDesc]), | |
| 595 | operation_cached_results(ID,Operation,PackedNewState,_PathInfo), | |
| 596 | translate_event_with_limit(Operation,100,OpStr), | |
| 597 | unpack_values(PackedNewState,NewState), translate:translate_bstate_limited(NewState,UpdateStr), | |
| 598 | format(' ~w -upd-> ~w~n',[OpStr,UpdateStr]), | |
| 599 | fail. | |
| 600 | print_op_cache_profile :- print_violated_invariants,fail. | |
| 601 | print_op_cache_profile :- ahc,print('----------'),nl. | |
| 602 | ||
| 603 | get_total_number_of_next_state_calls(OpNr,InvNr) :- | |
| 604 | get_counter(op_cache_id,TotNr), | |
| 605 | get_counter(inv_cache_nr,InvNr), | |
| 606 | OpNr is TotNr-InvNr. | |
| 607 | %findall(0,b_operation_cache:operation_computed(_Hash,_Op,_,_,_ID),Ls), length(Ls,Nr). | |
| 608 | ||
| 609 | get_op_cache_stats([next_state_calls-NrN, % actual calls to the B interpreter to compute next state | |
| 610 | operations_cached-NrC, % number of operations whose calls are cached | |
| 611 | invariants_cached-NrI, % number of invariants whose evaluation is cached | |
| 612 | next_state_guard_failures-NrFails, % number of next-state_call failures stored (disabled operation) | |
| 613 | reused_next_state_calls-SuccCalls, | |
| 614 | reused_next_state_failures-FailCalls, | |
| 615 | inv_check_calls-InvNr, % actual calls to check individual invariants in a state | |
| 616 | reused_inv_check_calls-SuccInvCalls | |
| 617 | ]) :- | |
| 618 | findall(OpKey,(operation_read_projection_cache(OpKey,OpName,_,_,_),atomic(OpName)),OK1), | |
| 619 | length(OK1,NrC), | |
| 620 | findall(OpKey,invariant_op_key(OpKey,_),OK2), | |
| 621 | length(OK2,NrI), | |
| 622 | findall(OpKey,(op_guard_fails(OpKey,_,_)),OK3), | |
| 623 | length(OK3,NrFails), | |
| 624 | get_total_number_of_next_state_calls(NrN,InvNr), | |
| 625 | get_counter(op_cached_failures,FailCalls), | |
| 626 | get_counter(op_cached_successes,SuccCalls), | |
| 627 | get_counter(inv_cached_successes,SuccInvCalls). | |
| 628 | ||
| 629 | % ---------------------- | |
| 630 | ||
| 631 | :- use_module(probsrc(tools_strings),[ajoin/2]). | |
| 632 | tcltk_op_cache_stats(list([list(['Operation','#Next-State', '#Results', | |
| 633 | '# Proj.Vars','Proj.Vars', 'ReadCsts', 'OnlyWritten'])|SEntries])) :- | |
| 634 | %b_get_machine_variables(Var),length(Var,VLen), | |
| 635 | findall(list([OP,NrCalls,RNr,NrProjVars,ProjVars,ReadConstants,AdditionalOutVars]), | |
| 636 | (operation_read_projection_cache(OpKey,OpName,ProjVars,_,AdditionalOutVars), | |
| 637 | (OpName = check_invariant_violated(Nr) -> ajoin(['Invariant',Nr],OP) ; OP=OpName), | |
| 638 | length(ProjVars,NrProjVars), | |
| 639 | operation_read_constants(OpKey,ReadConstants), | |
| 640 | get_nr_next_state_calls(OpName,NrCalls), | |
| 641 | get_nr_cache_results(OpName,RNr) | |
| 642 | ), Entries), sort(Entries,SEntries). | |
| 643 | ||
| 644 | % ---------------------- | |
| 645 | % DOT RENDERING (not yet finished) | |
| 646 | ||
| 647 | %op_cache_node(ID,OpName,NodeDesc,Shape,Style,Color) :- Shape=box, Style=solid, Color=blue, | |
| 648 | % operation_computed(_Hash,OpName,_,PackedState,ID), | |
| 649 | % unpack_values(PackedState,State), translate_bstate_limited(State,NodeDesc). | |
| 650 | %:- use_module(probsrc(dotsrc(dot_graph_generator)),[gen_dot_graph/3]). | |
| 651 | % Predicates for creating a dependency graph | |
| 652 | %tcltk_operation_cache_graph(File) :- gen_dot_graph(File,op_cache_node,cbc_dependence_trans_predicate). | |
| 653 |