wurstscript / WurstScript / 228

Committed 29 Nov 2023 05:00PM UTC coverage: 62.48% (-0.09%) from 62.574%

Build # 228

Build Type

push

circleci

Committed by

web-flow

Commit Message

Show dialog for choosing game path, cleanup (#1083)

* show dialog for choosing game path

* cleanup code

* remove logs and refactor

* remove confusing mpq error, make some mpq loads readonly

Run Details

17295 of 27681 relevant lines covered (62.48%)

0.62 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

89.82

de.peeeq.wurstscript/src/main/java/de/peeeq/wurstscript/intermediatelang/optimizer/LocalMerger.java

package de.peeeq.wurstscript.intermediatelang.optimizer;

import de.peeeq.datastructures.Worklist;
import de.peeeq.wurstscript.intermediatelang.optimizer.ControlFlowGraph.Node;
import de.peeeq.wurstscript.jassIm.*;
import de.peeeq.wurstscript.translation.imoptimizer.OptimizerPass;
import de.peeeq.wurstscript.translation.imtranslation.ImHelper;
import de.peeeq.wurstscript.translation.imtranslation.ImTranslator;
import de.peeeq.wurstscript.types.TypesHelper;
import io.vavr.collection.HashSet;
import io.vavr.collection.Set;

import java.util.*;

import static de.peeeq.wurstscript.translation.imtranslation.FunctionFlagEnum.IS_VARARG;

/**
 * merges local variable, if they have disjoint live-spans
 * <p>
 * the input must be a flattened program
 */
public class LocalMerger implements OptimizerPass {
    private int totalLocalsMerged = 0;

    @Override
    public int optimize(ImTranslator trans) {
        ImProg prog = trans.getImProg();
        totalLocalsMerged = 0;
        for (ImFunction func : ImHelper.calculateFunctionsOfProg(prog)) {
            if (!func.isNative() && !func.isBj()) {
                optimizeFunc(func);
            }
        }
        return totalLocalsMerged;
    }


    @Override
    public String getName() {
        return "Local variables merged";
    }

    void optimizeFunc(ImFunction func) {
        Map<ImStmt, Set<ImVar>> livenessInfo = calculateLiveness(func);
        eliminateDeadCode(livenessInfo);
        mergeLocals(livenessInfo, func);
    }

    private boolean canMerge(ImType a, ImType b) {
        return a.equalsType(b);
    }

    private void mergeLocals(Map<ImStmt, Set<ImVar>> livenessInfo, ImFunction func) {
        Map<ImVar, Set<ImVar>> inferenceGraph = calculateInferenceGraph(livenessInfo);

        // priority queue, sorted by number of inferring vars
        PriorityQueue<ImVar> vars = new PriorityQueue<>((ImVar a, ImVar b) ->
                inferenceGraph.get(b).size() - inferenceGraph.get(a).size());
        vars.addAll(inferenceGraph.keySet());
        // do not merge parameters (this would not work)
        vars.removeAll(func.getParameters());

        // variables which represent their own 'color', initially these are the parameters
        List<ImVar> assigned = new ArrayList<>(func.getParameters());
        if(func.hasFlag(IS_VARARG)) {
            assigned.remove(assigned.size() - 1);
        }
        Map<ImVar, ImVar> merges = new HashMap<>();

        nextVar:
        while (!vars.isEmpty()) {
            ImVar v = vars.poll();

            // check if there is some other variable which is already assigned, has the same type and does not interfere
            nextAssigned:
            for (ImVar other : assigned) {
                if (canMerge(other.getType(), v.getType()) ) {
                    for (ImVar inferingVar : inferenceGraph.get(v)) {
                        if (merges.getOrDefault(inferingVar, inferingVar) == other) {
                            // variable already used by infering var, try next color
                            continue nextAssigned;
                        }
                    }
                    // found a color to merge
                    merges.put(v, other);
                    continue nextVar;
                }
            }
            assigned.add(v);
        }

        totalLocalsMerged += merges.size();

        func.accept(new ImFunction.DefaultVisitor() {
            @Override
            public void visit(ImVarAccess va) {
                super.visit(va);
                ImVar v = va.getVar();
                if (merges.containsKey(v)) {
                    va.setVar(merges.get(v));
                }
            }

            @Override
            public void visit(ImSet set) {
                super.visit(set);
                if (set.getLeft() instanceof ImVarAccess) {
                    ImVar v = ((ImVarAccess) set.getLeft()).getVar();
                    if (merges.containsKey(v)) {
                        set.setLeft(JassIm.ImVarAccess(merges.get(v)));
                    }
                }
            }

            @Override
            public void visit(ImVarargLoop varargLoop) {
                super.visit(varargLoop);
                ImVar v = varargLoop.getLoopVar();
                if (merges.containsKey(v)) {
                    varargLoop.setLoopVar(merges.get(v));
                }
            }
        });
    }

    /**
     * for each variable: the set of variables which share some lifetime-range
     */
    private Map<ImVar, Set<ImVar>> calculateInferenceGraph(Map<ImStmt, Set<ImVar>> livenessInfo) {
        Map<ImVar, Set<ImVar>> inferenceGraph = new LinkedHashMap<>();
        java.util.Set<ImStmt> keys = livenessInfo.keySet();
        int i  = 0;
        for (ImStmt s : keys) {
            i++;
            Set<ImVar> live = livenessInfo.get(s);
            for (ImVar v1 : live) {
                Set<ImVar> inferenceSet = inferenceGraph.getOrDefault(v1, HashSet.empty());
                inferenceSet = inferenceSet.addAll(live.filter(v2 -> canMerge(v1.getType(), v2.getType()) ));
                inferenceGraph.put(v1, inferenceSet);
            }
        }
        return inferenceGraph;
    }

    private void eliminateDeadCode(Map<ImStmt, Set<ImVar>> livenessInfo) {
        for (ImStmt s : livenessInfo.keySet()) {
            if (s instanceof ImSet) {
                ImSet imSet = (ImSet) s;
                ImVar v = null;
                if(imSet.getLeft() instanceof ImVarAccess) {
                    ImVarAccess va = (ImVarAccess) imSet.getLeft();
                    v = va.getVar();
                } else if(imSet.getLeft() instanceof ImTupleSelection) {
                    v = TypesHelper.getSimpleAndPureTupleVar((ImTupleSelection) imSet.getLeft());
                }
                if (v == null || v.isGlobal()) {
                    continue;
                }

                if (!livenessInfo.get(s).contains(v)) {
                    // write to a variable which is not live
                    // --> only keep side effects
                    ImExpr right = imSet.getRight();
                    right.setParent(null);
                    s.replaceBy(right);
                }
            }
        }
    }


    public Map<ImStmt, Set<ImVar>> calculateLiveness(ImFunction func) {
        ControlFlowGraph cfg = new ControlFlowGraph(func.getBody());
        Map<Node, Set<ImVar>> in = new LinkedHashMap<>();
        Map<Node, Set<ImVar>> out = new LinkedHashMap<>();

        Worklist<Node> todo = new Worklist<>();

        Map<Node, Integer> index = new LinkedHashMap<>();

        // init in and out with empty sets
        for (Node node : cfg.getNodes()) {
            in.put(node, HashSet.empty());
            out.put(node, HashSet.empty());
            todo.addFirst(node);
            index.put(node, 1+ index.size());
        }

        // calculate def- and use- sets for each node
        Map<Node, Set<ImVar>> def = calculateDefs(cfg.getNodes());
        Map<Node, Set<ImVar>> use = calculateUses(cfg.getNodes());
        while (!todo.isEmpty()) {
            Node node = todo.poll();

            // out[n] = union s in succ[n]: in[s]
            Set<ImVar> newOut = node.getSuccessors()
                .stream()
                .map(in::get)
                .reduce(HashSet.empty(), Set::union);

            // in[n] = use[n] + (out[n] - def[n])
            Set<ImVar> newIn = newOut;
            newIn = newIn.diff(def.get(node));
            newIn = newIn.union(use.get(node));


            if (!newIn.equals(in.get(node))) {
                in.put(node, newIn);
                // if in changes, then all predecessors have to be recalculated
                for (Node pred : node.getPredecessors()) {
                    todo.addLast(pred);
                }
            }
            if (!newOut.equals(out.get(node))) {
                out.put(node, newOut);
            }
        }

        Map<ImStmt, Set<ImVar>> result = new LinkedHashMap<>();
        for (Node node : cfg.getNodes()) {
            ImStmt stmt = node.getStmt();
            if (stmt != null) {
                result.put(stmt, out.get(node));
            }
        }
        return result;
    }

    private Map<Node, Set<ImVar>> calculateUses(List<Node> nodes) {
        Map<Node, Set<ImVar>> result = new LinkedHashMap<>();
        for (Node node : nodes) {
            List<ImVar> uses = new ArrayList<>();
            ImStmt stmt = node.getStmt();
            if (stmt != null) {
                stmt.accept(new ImStmt.DefaultVisitor() {
                    @Override
                    public void visit(ImVarAccess va) {
                        super.visit(va);
                        if (!va.getVar().isGlobal()) {
                            uses.add(va.getVar());
                        }
                    }

                    @Override
                    public void visit(ImSet set) {
                        set.getRight().accept(this);
                        Element.DefaultVisitor outerThis = this;
                        set.getLeft().match(new ImLExpr.MatcherVoid() {
                            @Override
                            public void case_ImTupleSelection(ImTupleSelection e) {
                                ((ImLExpr) (e.getTupleExpr())).match(this);
                            }

                            @Override
                            public void case_ImVarAccess(ImVarAccess e) {
                            }

                            @Override
                            public void case_ImVarArrayAccess(ImVarArrayAccess e) {
                                e.getIndexes().accept(outerThis);
                            }

                            @Override
                            public void case_ImMemberAccess(ImMemberAccess e) {
                                e.getReceiver().accept(outerThis);
                                e.getIndexes().accept(outerThis);
                            }

                            @Override
                            public void case_ImStatementExpr(ImStatementExpr e) {
                                e.getStatements().accept(outerThis);
                                ((ImLExpr) e.getExpr()).match(this);
                            }

                            @Override
                            public void case_ImTupleExpr(ImTupleExpr e) {
                                for (ImExpr expr : e.getExprs()) {
                                    ((ImLExpr) expr).match(this);
                                }
                            }
                        });
                    }
                });
            }
            result.put(node, HashSet.ofAll(uses));
        }
        return result;
    }

    private Map<Node, Set<ImVar>> calculateDefs(List<Node> nodes) {
        Map<Node, Set<ImVar>>result = new LinkedHashMap<>();
        for (Node node : nodes) {
            result.put(node, HashSet.empty());
            ImStmt stmt = node.getStmt();
            if (stmt instanceof ImSet) {
                ImSet imSet = (ImSet) stmt;
                if (imSet.getLeft() instanceof ImVarAccess) {
                    ImVar v = ((ImVarAccess) imSet.getLeft()).getVar();
                    if (!v.isGlobal()) {
                        result.put(node, HashSet.of(v));
                    }
                }
                // no special case for tuple selection, as they do not override all previous values
            }
        }
        return result;
    }


}

1	package de.peeeq.wurstscript.intermediatelang.optimizer;
2
3	import de.peeeq.datastructures.Worklist;
4	import de.peeeq.wurstscript.intermediatelang.optimizer.ControlFlowGraph.Node;
5	import de.peeeq.wurstscript.jassIm.*;
6	import de.peeeq.wurstscript.translation.imoptimizer.OptimizerPass;
7	import de.peeeq.wurstscript.translation.imtranslation.ImHelper;
8	import de.peeeq.wurstscript.translation.imtranslation.ImTranslator;
9	import de.peeeq.wurstscript.types.TypesHelper;
10	import io.vavr.collection.HashSet;
11	import io.vavr.collection.Set;
12
13	import java.util.*;
14
15	import static de.peeeq.wurstscript.translation.imtranslation.FunctionFlagEnum.IS_VARARG;
16
17	/**
18	* merges local variable, if they have disjoint live-spans
19	* <p>
20	* the input must be a flattened program
21	*/
22	public class LocalMerger implements OptimizerPass {	1✔
23	private int totalLocalsMerged = 0;	1✔
24
25	@Override
26	public int optimize(ImTranslator trans) {
27	ImProg prog = trans.getImProg();	1✔
28	totalLocalsMerged = 0;	1✔
29	for (ImFunction func : ImHelper.calculateFunctionsOfProg(prog)) {	1✔
30	if (!func.isNative() && !func.isBj()) {	1✔
31	optimizeFunc(func);	1✔
32	}
33	}	1✔
34	return totalLocalsMerged;	1✔
35	}
36
37
38	@Override
39	public String getName() {
40	return "Local variables merged";	1✔
41	}
42
43	void optimizeFunc(ImFunction func) {
44	Map<ImStmt, Set<ImVar>> livenessInfo = calculateLiveness(func);	1✔
45	eliminateDeadCode(livenessInfo);	1✔
46	mergeLocals(livenessInfo, func);	1✔
47	}	1✔
48
49	private boolean canMerge(ImType a, ImType b) {
50	return a.equalsType(b);	1✔
51	}
52
53	private void mergeLocals(Map<ImStmt, Set<ImVar>> livenessInfo, ImFunction func) {
54	Map<ImVar, Set<ImVar>> inferenceGraph = calculateInferenceGraph(livenessInfo);	1✔
55
56	// priority queue, sorted by number of inferring vars
57	PriorityQueue<ImVar> vars = new PriorityQueue<>((ImVar a, ImVar b) ->	1✔
58	inferenceGraph.get(b).size() - inferenceGraph.get(a).size());	1✔
59	vars.addAll(inferenceGraph.keySet());	1✔
60	// do not merge parameters (this would not work)
61	vars.removeAll(func.getParameters());	1✔
62
63	// variables which represent their own 'color', initially these are the parameters
64	List<ImVar> assigned = new ArrayList<>(func.getParameters());	1✔
65	if(func.hasFlag(IS_VARARG)) {	1✔
66	assigned.remove(assigned.size() - 1);	×
67	}
68	Map<ImVar, ImVar> merges = new HashMap<>();	1✔
69
70	nextVar:
71	while (!vars.isEmpty()) {	1✔
72	ImVar v = vars.poll();	1✔
73
74	// check if there is some other variable which is already assigned, has the same type and does not interfere
75	nextAssigned:
76	for (ImVar other : assigned) {	1✔
77	if (canMerge(other.getType(), v.getType()) ) {	1✔
78	for (ImVar inferingVar : inferenceGraph.get(v)) {	1✔
79	if (merges.getOrDefault(inferingVar, inferingVar) == other) {	1✔
80	// variable already used by infering var, try next color
81	continue nextAssigned;	1✔
82	}
83	}	1✔
84	// found a color to merge
85	merges.put(v, other);	1✔
86	continue nextVar;	1✔
87	}
88	}	1✔
89	assigned.add(v);	1✔
90	}	1✔
91
92	totalLocalsMerged += merges.size();	1✔
93
94	func.accept(new ImFunction.DefaultVisitor() {	1✔
95	@Override
96	public void visit(ImVarAccess va) {
97	super.visit(va);	1✔
98	ImVar v = va.getVar();	1✔
99	if (merges.containsKey(v)) {	1✔
100	va.setVar(merges.get(v));	1✔
101	}
102	}	1✔
103
104	@Override
105	public void visit(ImSet set) {
106	super.visit(set);	1✔
107	if (set.getLeft() instanceof ImVarAccess) {	1✔
108	ImVar v = ((ImVarAccess) set.getLeft()).getVar();	1✔
109	if (merges.containsKey(v)) {	1✔
110	set.setLeft(JassIm.ImVarAccess(merges.get(v)));	×
111	}
112	}
113	}	1✔
114
115	@Override
116	public void visit(ImVarargLoop varargLoop) {
117	super.visit(varargLoop);	×
118	ImVar v = varargLoop.getLoopVar();	×
119	if (merges.containsKey(v)) {	×
120	varargLoop.setLoopVar(merges.get(v));	×
121	}
122	}	×
123	});
124	}	1✔
125
126	/**
127	* for each variable: the set of variables which share some lifetime-range
128	*/
129	private Map<ImVar, Set<ImVar>> calculateInferenceGraph(Map<ImStmt, Set<ImVar>> livenessInfo) {
130	Map<ImVar, Set<ImVar>> inferenceGraph = new LinkedHashMap<>();	1✔
131	java.util.Set<ImStmt> keys = livenessInfo.keySet();	1✔
132	int i = 0;	1✔
133	for (ImStmt s : keys) {	1✔
134	i++;	1✔
135	Set<ImVar> live = livenessInfo.get(s);	1✔
136	for (ImVar v1 : live) {	1✔
137	Set<ImVar> inferenceSet = inferenceGraph.getOrDefault(v1, HashSet.empty());	1✔
138	inferenceSet = inferenceSet.addAll(live.filter(v2 -> canMerge(v1.getType(), v2.getType()) ));	1✔
139	inferenceGraph.put(v1, inferenceSet);	1✔
140	}	1✔
141	}	1✔
142	return inferenceGraph;	1✔
143	}
144
145	private void eliminateDeadCode(Map<ImStmt, Set<ImVar>> livenessInfo) {
146	for (ImStmt s : livenessInfo.keySet()) {	1✔
147	if (s instanceof ImSet) {	1✔
148	ImSet imSet = (ImSet) s;	1✔
149	ImVar v = null;	1✔
150	if(imSet.getLeft() instanceof ImVarAccess) {	1✔
151	ImVarAccess va = (ImVarAccess) imSet.getLeft();	1✔
152	v = va.getVar();	1✔
153	} else if(imSet.getLeft() instanceof ImTupleSelection) {	1✔
154	v = TypesHelper.getSimpleAndPureTupleVar((ImTupleSelection) imSet.getLeft());	×
155	}
156	if (v == null \|\| v.isGlobal()) {	1✔
157	continue;	1✔
158	}
159
160	if (!livenessInfo.get(s).contains(v)) {	1✔
161	// write to a variable which is not live
162	// --> only keep side effects
163	ImExpr right = imSet.getRight();	1✔
164	right.setParent(null);	1✔
165	s.replaceBy(right);	1✔
166	}
167	}
168	}	1✔
169	}	1✔
170
171
172	public Map<ImStmt, Set<ImVar>> calculateLiveness(ImFunction func) {
173	ControlFlowGraph cfg = new ControlFlowGraph(func.getBody());	1✔
174	Map<Node, Set<ImVar>> in = new LinkedHashMap<>();	1✔
175	Map<Node, Set<ImVar>> out = new LinkedHashMap<>();	1✔
176
177	Worklist<Node> todo = new Worklist<>();	1✔
178
179	Map<Node, Integer> index = new LinkedHashMap<>();	1✔
180
181	// init in and out with empty sets
182	for (Node node : cfg.getNodes()) {	1✔
183	in.put(node, HashSet.empty());	1✔
184	out.put(node, HashSet.empty());	1✔
185	todo.addFirst(node);	1✔
186	index.put(node, 1+ index.size());	1✔
187	}	1✔
188
189	// calculate def- and use- sets for each node
190	Map<Node, Set<ImVar>> def = calculateDefs(cfg.getNodes());	1✔
191	Map<Node, Set<ImVar>> use = calculateUses(cfg.getNodes());	1✔
192	while (!todo.isEmpty()) {	1✔
193	Node node = todo.poll();	1✔
194
195	// out[n] = union s in succ[n]: in[s]
196	Set<ImVar> newOut = node.getSuccessors()	1✔
197	.stream()	1✔
198	.map(in::get)	1✔
199	.reduce(HashSet.empty(), Set::union);	1✔
200
201	// in[n] = use[n] + (out[n] - def[n])
202	Set<ImVar> newIn = newOut;	1✔
203	newIn = newIn.diff(def.get(node));	1✔
204	newIn = newIn.union(use.get(node));	1✔
205
206
207	if (!newIn.equals(in.get(node))) {	1✔
208	in.put(node, newIn);	1✔
209	// if in changes, then all predecessors have to be recalculated
210	for (Node pred : node.getPredecessors()) {	1✔
211	todo.addLast(pred);	1✔
212	}	1✔
213	}
214	if (!newOut.equals(out.get(node))) {	1✔
215	out.put(node, newOut);	1✔
216	}
217	}	1✔
218
219	Map<ImStmt, Set<ImVar>> result = new LinkedHashMap<>();	1✔
220	for (Node node : cfg.getNodes()) {	1✔
221	ImStmt stmt = node.getStmt();	1✔
222	if (stmt != null) {	1✔
223	result.put(stmt, out.get(node));	1✔
224	}
225	}	1✔
226	return result;	1✔
227	}
228
229	private Map<Node, Set<ImVar>> calculateUses(List<Node> nodes) {
230	Map<Node, Set<ImVar>> result = new LinkedHashMap<>();	1✔
231	for (Node node : nodes) {	1✔
232	List<ImVar> uses = new ArrayList<>();	1✔
233	ImStmt stmt = node.getStmt();	1✔
234	if (stmt != null) {	1✔
235	stmt.accept(new ImStmt.DefaultVisitor() {	1✔
236	@Override
237	public void visit(ImVarAccess va) {
238	super.visit(va);	1✔
239	if (!va.getVar().isGlobal()) {	1✔
240	uses.add(va.getVar());	1✔
241	}
242	}	1✔
243
244	@Override
245	public void visit(ImSet set) {
246	set.getRight().accept(this);	1✔
247	Element.DefaultVisitor outerThis = this;	1✔
248	set.getLeft().match(new ImLExpr.MatcherVoid() {	1✔
249	@Override
250	public void case_ImTupleSelection(ImTupleSelection e) {
251	((ImLExpr) (e.getTupleExpr())).match(this);	×
252	}	×
253
254	@Override
255	public void case_ImVarAccess(ImVarAccess e) {
256	}	1✔
257
258	@Override
259	public void case_ImVarArrayAccess(ImVarArrayAccess e) {
260	e.getIndexes().accept(outerThis);	1✔
261	}	1✔
262
263	@Override
264	public void case_ImMemberAccess(ImMemberAccess e) {
265	e.getReceiver().accept(outerThis);	1✔
266	e.getIndexes().accept(outerThis);	1✔
267	}	1✔
268
269	@Override
270	public void case_ImStatementExpr(ImStatementExpr e) {
271	e.getStatements().accept(outerThis);	×
272	((ImLExpr) e.getExpr()).match(this);	×
273	}	×
274
275	@Override
276	public void case_ImTupleExpr(ImTupleExpr e) {
277	for (ImExpr expr : e.getExprs()) {	×
278	((ImLExpr) expr).match(this);	×
279	}	×
280	}	×
281	});
282	}	1✔
283	});
284	}
285	result.put(node, HashSet.ofAll(uses));	1✔
286	}	1✔
287	return result;	1✔
288	}
289
290	private Map<Node, Set<ImVar>> calculateDefs(List<Node> nodes) {
291	Map<Node, Set<ImVar>>result = new LinkedHashMap<>();	1✔
292	for (Node node : nodes) {	1✔
293	result.put(node, HashSet.empty());	1✔
294	ImStmt stmt = node.getStmt();	1✔
295	if (stmt instanceof ImSet) {	1✔
296	ImSet imSet = (ImSet) stmt;	1✔
297	if (imSet.getLeft() instanceof ImVarAccess) {	1✔
298	ImVar v = ((ImVarAccess) imSet.getLeft()).getVar();	1✔
299	if (!v.isGlobal()) {	1✔
300	result.put(node, HashSet.of(v));	1✔
301	}
302	}
303	// no special case for tuple selection, as they do not override all previous values
304	}
305	}	1✔
306	return result;	1✔
307	}
308
309
310	}

wurstscript / WurstScript / 228

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous