1 | % (c) 2009-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(static_ordering,[sort_ids_by_usage/3, sort_ids_by_usage/4, reorder_state/3]). | |
6 | ||
7 | :- use_module(module_information). | |
8 | :- module_info(group,tools). | |
9 | :- module_info(description,'Sort a list of identifiers according to the number of occurences inside conjuncts of a predicate. Mimics the static ordering heursitic of SAT solvers'). | |
10 | ||
11 | :- use_module(bsyntaxtree,[find_identifier_uses/3,def_get_texpr_id/2]). | |
12 | ||
13 | :- use_module(error_manager). | |
14 | ||
15 | :- dynamic used/2. | |
16 | % put most used IDs towards the front; these will be enumerated first | |
17 | sort_ids_by_usage(IDs,Predicate,SortedIDs) :- | |
18 | sort_ids_by_usage(IDs,Predicate,SortedIDs,warnings). | |
19 | sort_ids_by_usage(IDs,Predicate,SortedIDs,WARN) :- | |
20 | retractall(used(_,_)), | |
21 | count_uses(Predicate), | |
22 | sort_according_to_usage(IDs,SIDs,WARN), | |
23 | %% print(SIDs),nl, %% | |
24 | project_used_id(SIDs,SortedIDs). | |
25 | ||
26 | count_uses(Var) :- var(Var),!, add_internal_error('Variable AST:',count_uses(Var)),fail. | |
27 | count_uses(b(conjunct(LHS,RHS),pred,_)) :- !, | |
28 | count_uses(LHS), count_uses(RHS). | |
29 | count_uses(X) :- % translate:print_bexpr(X),nl, | |
30 | find_identifier_uses(X,[],IDs), | |
31 | %% print(usage(IDs)),nl,%% | |
32 | add_usage(IDs). | |
33 | add_usage([]). | |
34 | add_usage([ID|T]) :- (retract(used(ID,Nr)) -> true ; Nr=0), | |
35 | N1 is Nr+1, assertz(used(ID,N1)), | |
36 | add_usage(T). | |
37 | ||
38 | sort_according_to_usage([],[],_). | |
39 | sort_according_to_usage([TID|T],Res,WARN) :- | |
40 | def_get_texpr_id(TID,ID), | |
41 | (used(ID,Nr) -> true %%print(used(ID,Nr)),nl | |
42 | ; (WARN==warnings | |
43 | -> add_message(sort_according_to_usage,'### Unused identifier: ',ID) | |
44 | ; true), | |
45 | Nr=0), | |
46 | sort_according_to_usage(T,TSorted,WARN), % recurse first for stability of sorting | |
47 | insert_used_id(TSorted,TID,Nr,Res). | |
48 | insert_used_id([],TID,Nr,[(TID,Nr)]). | |
49 | insert_used_id([(H,HNr)|T],TID,Nr,Res) :- | |
50 | (Nr>=HNr -> Res = [(TID,Nr),(H,HNr)|T] | |
51 | ; Res=[(H,HNr)|RT], insert_used_id(T,TID,Nr,RT) | |
52 | ). | |
53 | ||
54 | project_used_id([],[]). | |
55 | project_used_id([(A,_)|T],[A|PT]) :- project_used_id(T,PT). | |
56 | ||
57 | ||
58 | % -------------- | |
59 | ||
60 | ||
61 | :- use_module(library(lists),[select/3]). | |
62 | :- use_module(bsyntaxtree,[def_get_texpr_id/2]). | |
63 | ||
64 | % reorder state into original order, to avoid issues with state_packing or ltsmin | |
65 | reorder_state([],Rest,Rest). | |
66 | reorder_state([TID|T],InState,[bind(ID,V)|OutState]) :- def_get_texpr_id(TID,ID), | |
67 | select(bind(ID,V),InState,Rest), reorder_state(T,Rest,OutState). | |
68 |