• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

wurstscript / WurstScript / 271

29 Sep 2025 12:12PM UTC coverage: 64.649% (+2.4%) from 62.222%
271

Pull #1096

circleci

Frotty
Merge branch 'perf-improvements' of https://github.com/wurstscript/WurstScript into perf-improvements
Pull Request #1096: Perf improvements

18202 of 28155 relevant lines covered (64.65%)

0.65 hits per line

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

97.96
de.peeeq.wurstscript/src/main/java/de/peeeq/wurstscript/translation/imtranslation/CyclicFunctionRemover.java
1
package de.peeeq.wurstscript.translation.imtranslation;
2

3
import com.google.common.collect.ImmutableList;
4
import com.google.common.collect.Lists;
5
import com.google.common.collect.Maps;
6
import de.peeeq.datastructures.GraphInterpreter;
7
import de.peeeq.wurstio.TimeTaker;
8
import de.peeeq.wurstscript.WurstOperator;
9
import de.peeeq.wurstscript.jassIm.*;
10
import de.peeeq.wurstscript.types.WurstTypeInt;
11

12
import java.util.*;
13
import java.util.concurrent.atomic.AtomicReference;
14

15
/**
16
 * Removes cyclic functions from a program
17
 * by putting cyclic functions into one big function
18
 */
19
public class CyclicFunctionRemover {
20

21

22
    private final ImProg prog;
23
    private final TimeTaker timeTaker;
24
    private final ImTranslator tr;
25
    private final ImFuncGraph graph;
26

27
    public CyclicFunctionRemover(ImTranslator tr, ImProg prog, TimeTaker timeTaker) {
1✔
28
        this.tr = tr;
1✔
29
        this.prog = prog;
1✔
30
        this.timeTaker = timeTaker;
1✔
31
        this.graph = new ImFuncGraph();
1✔
32
    }
1✔
33

34
    public void work() {
35
        tr.calculateCallRelationsAndUsedVariables();
1✔
36
        AtomicReference<List<List<ImFunction>>> components = new AtomicReference<>();
1✔
37
        timeTaker.measure("finding cycles",
1✔
38
            () -> components.set(graph.findStronglyConnectedComponents(prog.getFunctions()))
1✔
39
        );
40
        timeTaker.measure("removing cycles", () -> removeCycles(components));
1✔
41
    }
1✔
42

43
    private void removeCycles(AtomicReference<List<List<ImFunction>>> componentsRef) {
44
        for (List<ImFunction> component : componentsRef.get()) {
1✔
45
            if (component.size() > 1) {
1✔
46
                // keep list for order; set for O(1) membership
47
                Set<ImFunction> funcSet = new HashSet<>(component);
1✔
48
                removeCycle(component, funcSet);
1✔
49
            }
50
        }
1✔
51
    }
1✔
52

53
    private void removeCycle(List<ImFunction> funcs, Set<ImFunction> funcSet) {
54
        List<ImVar> newParameters = Lists.newArrayList();
1✔
55
        Map<ImVar, ImVar> oldToNewVar = Maps.newLinkedHashMap();
1✔
56

57
        calculateNewParameters(funcs, newParameters, oldToNewVar);
1✔
58

59
        de.peeeq.wurstscript.ast.Element trace = funcs.get(0).getTrace();
1✔
60

61
        ImVar choiceVar = JassIm.ImVar(trace, WurstTypeInt.instance().imTranslateType(tr), "funcChoice", false);
1✔
62

63
        List<FunctionFlag> flags = Lists.newArrayList();
1✔
64

65
        ImFunction newFunc = JassIm.ImFunction(trace, makeName(funcs), JassIm.ImTypeVars(), JassIm.ImVars(), JassIm.ImVoid(), JassIm.ImVars(), JassIm.ImStmts(), flags);
1✔
66
        prog.getFunctions().add(newFunc);
1✔
67
        newFunc.getParameters().add(choiceVar);
1✔
68
        newFunc.getParameters().addAll(newParameters);
1✔
69

70
        ImStmts stmts = newFunc.getBody();
1✔
71

72
        for (int i = 0; i < funcs.size(); i++) {
1✔
73
            ImFunction f = funcs.get(i);
1✔
74
            ImStmts thenBlock = JassIm.ImStmts();
1✔
75

76
            // add body
77
            thenBlock.addAll(f.getBody().removeAll());
1✔
78
            // addLocals
79
            newFunc.getLocals().addAll(f.getLocals().removeAll());
1✔
80

81
            replaceVars(thenBlock, oldToNewVar);
1✔
82

83
            if (!(f.getReturnType() instanceof ImVoid)) {
1✔
84
                replaceReturn(thenBlock, f.getReturnType());
1✔
85
            }
86

87
            ImStmts elseBlock = JassIm.ImStmts();
1✔
88
            stmts.add(JassIm.ImIf(trace,
1✔
89
                    JassIm.ImOperatorCall(WurstOperator.EQ,
1✔
90
                            JassIm.ImExprs(JassIm.ImVarAccess(choiceVar), JassIm.ImIntVal(i))),
1✔
91
                    thenBlock,
92
                    elseBlock));
93
            stmts = elseBlock;
1✔
94
        }
95

96
        Map<ImFunction, Integer> funcToIndex = new HashMap<>();
1✔
97
        for (int i = 0; i < funcs.size(); i++) {
1✔
98
            funcToIndex.put(funcs.get(i), i);
1✔
99
        }
100
        replaceCalls(funcSet, funcToIndex, newFunc, oldToNewVar, prog);
1✔
101

102
        for (ImFunction e : Lists.newArrayList(tr.getCalledFunctions().keys())) {
1✔
103
            Collection<ImFunction> called = tr.getCalledFunctions().get(e);
1✔
104
            called.removeAll(funcs);
1✔
105
        }
1✔
106

107
        // remove the old funcs
108
        prog.getFunctions().removeAll(funcs);
1✔
109
//                System.out.println("----------------------------------");
110
//                System.out.println(prog.toString());
111
//                System.out.println("----------------------------------");
112
    }
1✔
113

114
    private void replaceVars(Element e, Map<ImVar, ImVar> oldToNewVar) {
115
        // process children
116
        for (int i = 0; i < e.size(); i++) {
1✔
117
            replaceVars(e.get(i), oldToNewVar);
1✔
118
        }
119

120
        if (e instanceof ImVarAccess) {
1✔
121
            ImVarAccess va = (ImVarAccess) e;
1✔
122
            ImVar newVar = oldToNewVar.get(va.getVar());
1✔
123
            if (newVar != null) {
1✔
124
                va.setVar(newVar);
1✔
125
            }
126
        }
127
    }
1✔
128

129

130
    private void replaceCalls(Set<ImFunction> funcSet, Map<ImFunction, Integer> funcToIndex, ImFunction newFunc, Map<ImVar, ImVar> oldToNewVar, Element e) {
131
        List<Element> relevant = new ArrayList<>();
1✔
132
        e.accept(new Element.DefaultVisitor() {
1✔
133
            @Override
134
            public void visit(ImFuncRef imFuncRef) {
135
                super.visit(imFuncRef);
1✔
136
                relevant.add(imFuncRef);
1✔
137
            }
1✔
138

139
            @Override
140
            public void visit(ImFunctionCall imFunctionCall) {
141
                super.visit(imFunctionCall);
1✔
142
                relevant.add(imFunctionCall);
1✔
143
            }
1✔
144
        });
145
        relevant.parallelStream().forEach(relevantElem -> {
1✔
146
            if (relevantElem instanceof ImFuncRef) {
1✔
147
                replaceImFuncRef(funcSet, funcToIndex, newFunc, oldToNewVar, (ImFuncRef) relevantElem);
1✔
148
            } else if (relevantElem instanceof ImFunctionCall) {
1✔
149
                replaceImFunctionCall(funcSet, funcToIndex, newFunc, oldToNewVar, (ImFunctionCall) relevantElem);
1✔
150
            }
151
        });
1✔
152
    }
1✔
153

154
    private void replaceImFuncRef(Set<ImFunction> funcSet, Map<ImFunction, Integer> funcToIndex, ImFunction newFunc, Map<ImVar, ImVar> oldToNewVar, ImFuncRef e) {
155
        ImFuncRef fr = e;
1✔
156
        ImFunction f = fr.getFunc();
1✔
157
        if (funcSet.contains(f)) {
1✔
158

159
            ImFunction proxyFunc = JassIm.ImFunction(f.attrTrace(), f.getName() + "_proxy", JassIm.ImTypeVars(), f.getParameters().copy(), f.getReturnType().copy(), JassIm.ImVars(), JassIm.ImStmts(), Collections.emptyList());
1✔
160
            prog.getFunctions().add(proxyFunc);
1✔
161

162
            ImExprs arguments = JassIm.ImExprs();
1✔
163
            for (ImVar p : proxyFunc.getParameters()) {
1✔
164
                arguments.add(JassIm.ImVarAccess(p));
×
165
            }
×
166

167
            ImFunctionCall call = JassIm.ImFunctionCall(fr.attrTrace(), f, JassIm.ImTypeArguments(), arguments, true, CallType.NORMAL);
1✔
168

169
            if (f.getReturnType() instanceof ImVoid) {
1✔
170
                proxyFunc.getBody().add(call);
×
171
            } else {
172
                proxyFunc.getBody().add(JassIm.ImReturn(proxyFunc.getTrace(), call));
1✔
173
            }
174
            // rewrite the proxy call:
175
            replaceCalls(funcSet, funcToIndex, newFunc, oldToNewVar, call);
1✔
176
            // change the funcref to use the proxy
177
            fr.setFunc(proxyFunc);
1✔
178
        }
179
    }
1✔
180

181
    private void replaceImFunctionCall(Set<ImFunction> funcSet, Map<ImFunction, Integer> funcToIndex, ImFunction newFunc, Map<ImVar, ImVar> oldToNewVar, ImFunctionCall e) {
182
        ImFunctionCall fc = e;
1✔
183
        ImFunction oldFunc = fc.getFunc();
1✔
184
        if (funcSet.contains(oldFunc)) {
1✔
185

186
            ImExprs arguments = JassIm.ImExprs();
1✔
187

188
            // first argument is the choice index
189
            arguments.add(JassIm.ImIntVal(funcToIndex.get(oldFunc)));
1✔
190

191
            // now for the actual arguments
192
            List<ImExpr> oldArgs = fc.getArguments().removeAll();
1✔
193
            int pos = 0;
1✔
194
            for (int i = 1; i < newFunc.getParameters().size(); i++) {
1✔
195
                ImVar p = newFunc.getParameters().get(i);
1✔
196
                if (pos < oldArgs.size() && oldToNewVar.get(oldFunc.getParameters().get(pos)) == p) {
1✔
197
                    arguments.add(oldArgs.get(pos));
1✔
198
                    pos++;
1✔
199
                } else {
200
                    // use default value
201
                    arguments.add(tr.getDefaultValueForJassType(p.getType()));
1✔
202
                }
203
            }
204

205

206
            ImFunctionCall newCall = JassIm.ImFunctionCall(fc.getTrace(), newFunc, JassIm.ImTypeArguments(), arguments, true, CallType.NORMAL);
1✔
207

208
            Element ret;
209
            if (oldFunc.getReturnType() instanceof ImVoid) {
1✔
210
                ret = newCall;
1✔
211
            } else {
212
                // if there is a return value, use the temporary return value
213
                ret = JassIm.ImStatementExpr(JassIm.ImStmts(newCall), JassIm.ImVarAccess(getTempReturnVar(oldFunc.getReturnType())));
1✔
214
            }
215
            fc.replaceBy(ret);
1✔
216

217
        }
218
    }
1✔
219

220
    private void replaceReturn(Element e, ImType returnType) {
221
        // process children
222
        for (int i = 0; i < e.size(); i++) {
1✔
223
            replaceReturn(e.get(i), returnType);
1✔
224
        }
225

226

227
        if (e instanceof ImReturn) {
1✔
228
            ImReturn r = (ImReturn) e;
1✔
229

230
            ImExprOpt returnValue = r.getReturnValue();
1✔
231
            returnValue.setParent(null);
1✔
232
            ImStmts stmts = JassIm.ImStmts(
1✔
233
                    JassIm.ImSet(r.getTrace(), JassIm.ImVarAccess(getTempReturnVar(returnType)), (ImExpr) returnValue),
1✔
234
                    JassIm.ImReturn(r.getTrace(), JassIm.ImNoExpr())
1✔
235
            );
236
            r.replaceBy(ImHelper.statementExprVoid(stmts));
1✔
237
        }
238

239
    }
1✔
240

241
    private final Map<String, ImVar> tempReturnVars = Maps.newLinkedHashMap();
1✔
242

243
    private ImVar getTempReturnVar(ImType t) {
244
        String typeName = t.translateType();
1✔
245
        ImVar r = tempReturnVars.get(typeName);
1✔
246
        if (r == null) {
1✔
247
            r = JassIm.ImVar(t.attrTrace(), t, "tempReturn_" + typeName, false);
1✔
248
            prog.getGlobals().add(r);
1✔
249
            tempReturnVars.put(typeName, r);
1✔
250
        }
251
        return r;
1✔
252
    }
253

254
    private String makeName(List<ImFunction> funcs) {
255
        return "cyc_" + funcs.get(0).getName();
1✔
256
    }
257

258
    private void calculateNewParameters(List<ImFunction> funcs,
259
                                        List<ImVar> newParameters, Map<ImVar, ImVar> oldToNewVar) {
260
        for (ImFunction f : funcs) {
1✔
261
            int pos = 0;
1✔
262
            withNextParameter:
263
            for (ImVar v : f.getParameters()) {
1✔
264
                // first check if we can reuse a parameter from the newParameters
265
                for (int i = pos; i < newParameters.size(); i++) {
1✔
266
                    if (newParameters.get(i).getType().translateType().equals(v.getType().translateType())) {
1✔
267
                        // found a var we can reuse
268
                        oldToNewVar.put(v, newParameters.get(i));
1✔
269
                        pos = i + 1;
1✔
270
                        continue withNextParameter;
1✔
271
                    }
272
                }
273
                // otherwise, we have to create a new var:
274
                ImVar newVar = JassIm.ImVar(v.getTrace(), v.getType().copy(), v.getName(), false);
1✔
275
                oldToNewVar.put(v, newVar);
1✔
276
                newParameters.add(newVar);
1✔
277
                pos = newParameters.size() + 1;
1✔
278
            }
1✔
279
        }
1✔
280
    }
1✔
281

282
    class ImFuncGraph extends GraphInterpreter<ImFunction> {
1✔
283

284
        @Override
285
        protected Collection<ImFunction> getIncidentNodes(ImFunction f) {
286
            return tr.getCalledFunctions().get(f);
1✔
287
        }
288

289
    }
290

291

292
}
293

294

STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2025 Coveralls, Inc