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