Skip to content

Commit 22d24fd

Browse files
kripkenkripken
authored
[NFC] Move and generalize parameter-removing logic from DeadArgumentElimination (WebAssembly#4544)
In preparation for removing dead arguments from all functions sharing a heap type (which seems useful for j2wasm output), first this PR refactors that code so it is reusable. This moves the code out of the pass into FunctionUtils, and also generalizes it slightly by supporting a set of functions and not just a single one, and receiving a list of call_refs and not just calls (no other changes to anything).
1 parent ff762d2 commit 22d24fd

4 files changed

Lines changed: 267 additions & 101 deletions

File tree

‎src/passes/CMakeLists.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@ configure_file(WasmIntrinsics.cpp.in WasmIntrinsics.cpp @ONLY)
1313

1414
FILE(GLOB passes_HEADERS *.h)
1515
set(passes_SOURCES
16+
param-utils.cpp
1617
pass.cpp
1718
test_passes.cpp
1819
AlignmentLowering.cpp

‎src/passes/DeadArgumentElimination.cpp‎

Lines changed: 10 additions & 101 deletions
Original file line numberDiff line numberDiff line change
@@ -40,11 +40,11 @@
4040
#include "ir/effects.h"
4141
#include "ir/element-utils.h"
4242
#include "ir/find_all.h"
43-
#include "ir/local-graph.h"
4443
#include "ir/lubs.h"
4544
#include "ir/module-utils.h"
4645
#include "ir/type-updating.h"
4746
#include "ir/utils.h"
47+
#include "param-utils.h"
4848
#include "pass.h"
4949
#include "passes/opt-utils.h"
5050
#include "support/sorted_vector.h"
@@ -155,41 +155,13 @@ struct DAEScanner
155155
// part of, say if we are exported, or if another parallel function finds a
156156
// RefFunc to us and updates it before we check it).
157157
if (numParams > 0 && !info->hasUnseenCalls) {
158-
findUnusedParams(func);
159-
}
160-
}
161-
162-
void findUnusedParams(Function* func) {
163-
LocalGraph localGraph(func);
164-
std::unordered_set<Index> usedParams;
165-
for (auto& [get, sets] : localGraph.getSetses) {
166-
if (!func->isParam(get->index)) {
167-
continue;
168-
}
169-
170-
// Check if this get of a param index can read from the parameter value
171-
// passed into the function. We want to ignore values set in the function
172-
// like this:
173-
//
174-
// function foo(x) {
175-
// x = 10;
176-
// bar(x); // read of a param index, but not the param value passed in.
177-
// }
178-
for (auto* set : sets) {
179-
// A nullptr value indicates there is no LocalSet* that sets the value,
180-
// so it must be the parameter value.
181-
if (!set) {
182-
usedParams.insert(get->index);
158+
auto usedParams = ParamUtils::getUsedParams(func);
159+
for (Index i = 0; i < numParams; i++) {
160+
if (usedParams.count(i) == 0) {
161+
info->unusedParams.insert(i);
183162
}
184163
}
185164
}
186-
187-
// We can now compute the unused params.
188-
for (Index i = 0; i < numParams; i++) {
189-
if (usedParams.count(i) == 0) {
190-
info->unusedParams.insert(i);
191-
}
192-
}
193165
}
194166
};
195167

@@ -315,38 +287,11 @@ struct DAE : public Pass {
315287
if (numParams == 0) {
316288
continue;
317289
}
318-
// Iterate downwards, as we may remove more than one.
319-
Index i = numParams - 1;
320-
while (1) {
321-
if (infoMap[name].unusedParams.has(i)) {
322-
// Great, it's not used. Check if none of the calls has a param with
323-
// side effects that we cannot remove (as if we can remove them, we
324-
// will simply do that when we remove the parameter). Note: flattening
325-
// the IR beforehand can help here.
326-
bool callParamsAreValid =
327-
std::none_of(calls.begin(), calls.end(), [&](Call* call) {
328-
auto* operand = call->operands[i];
329-
return EffectAnalyzer(runner->options, *module, operand)
330-
.hasUnremovableSideEffects();
331-
});
332-
// The type must be valid for us to handle as a local (since we
333-
// replace the parameter with a local).
334-
// TODO: if there are no references at all, we can avoid creating a
335-
// local
336-
bool typeIsValid =
337-
TypeUpdating::canHandleAsLocal(func->getLocalType(i));
338-
if (callParamsAreValid && typeIsValid) {
339-
// Wonderful, nothing stands in our way! Do it.
340-
// TODO: parallelize this?
341-
removeParameter(func, i, calls);
342-
TypeUpdating::handleNonDefaultableLocals(func, *module);
343-
changed.insert(func);
344-
}
345-
}
346-
if (i == 0) {
347-
break;
348-
}
349-
i--;
290+
auto removedIndexes = ParamUtils::removeParameters(
291+
{func}, infoMap[name].unusedParams, calls, {}, module, runner);
292+
if (!removedIndexes.empty()) {
293+
// Success!
294+
changed.insert(func);
350295
}
351296
}
352297
// We can also tell which calls have all their return values dropped. Note
@@ -395,42 +340,6 @@ struct DAE : public Pass {
395340
private:
396341
std::unordered_map<Call*, Expression**> allDroppedCalls;
397342

398-
void removeParameter(Function* func, Index i, std::vector<Call*>& calls) {
399-
// It's cumbersome to adjust local names - TODO don't clear them?
400-
Builder::clearLocalNames(func);
401-
// Remove the parameter from the function. We must add a new local
402-
// for uses of the parameter, but cannot make it use the same index
403-
// (in general).
404-
auto paramsType = func->getParams();
405-
std::vector<Type> params(paramsType.begin(), paramsType.end());
406-
auto type = params[i];
407-
params.erase(params.begin() + i);
408-
func->setParams(Type(params));
409-
Index newIndex = Builder::addVar(func, type);
410-
// Update local operations.
411-
struct LocalUpdater : public PostWalker<LocalUpdater> {
412-
Index removedIndex;
413-
Index newIndex;
414-
LocalUpdater(Function* func, Index removedIndex, Index newIndex)
415-
: removedIndex(removedIndex), newIndex(newIndex) {
416-
walk(func->body);
417-
}
418-
void visitLocalGet(LocalGet* curr) { updateIndex(curr->index); }
419-
void visitLocalSet(LocalSet* curr) { updateIndex(curr->index); }
420-
void updateIndex(Index& index) {
421-
if (index == removedIndex) {
422-
index = newIndex;
423-
} else if (index > removedIndex) {
424-
index--;
425-
}
426-
}
427-
} localUpdater(func, i, newIndex);
428-
// Remove the arguments from the calls.
429-
for (auto* call : calls) {
430-
call->operands.erase(call->operands.begin() + i);
431-
}
432-
}
433-
434343
void
435344
removeReturnValue(Function* func, std::vector<Call*>& calls, Module* module) {
436345
func->setResults(Type::none);

‎src/passes/param-utils.cpp‎

Lines changed: 177 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,177 @@
1+
/*
2+
* Copyright 2022 WebAssembly Community Group participants
3+
*
4+
* Licensed under the Apache License, Version 2.0 (the "License");
5+
* you may not use this file except in compliance with the License.
6+
* You may obtain a copy of the License at
7+
*
8+
* http://www.apache.org/licenses/LICENSE-2.0
9+
*
10+
* Unless required by applicable law or agreed to in writing, software
11+
* distributed under the License is distributed on an "AS IS" BASIS,
12+
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13+
* See the License for the specific language governing permissions and
14+
* limitations under the License.
15+
*/
16+
17+
#include "ir/function-utils.h"
18+
#include "ir/local-graph.h"
19+
#include "ir/type-updating.h"
20+
#include "support/sorted_vector.h"
21+
#include "wasm.h"
22+
23+
namespace wasm::ParamUtils {
24+
25+
std::unordered_set<Index> getUsedParams(Function* func) {
26+
LocalGraph localGraph(func);
27+
28+
std::unordered_set<Index> usedParams;
29+
30+
for (auto& [get, sets] : localGraph.getSetses) {
31+
if (!func->isParam(get->index)) {
32+
continue;
33+
}
34+
35+
for (auto* set : sets) {
36+
// A nullptr value indicates there is no LocalSet* that sets the value,
37+
// so it must be the parameter value.
38+
if (!set) {
39+
usedParams.insert(get->index);
40+
}
41+
}
42+
}
43+
44+
return usedParams;
45+
}
46+
47+
bool removeParameter(const std::vector<Function*> funcs,
48+
Index index,
49+
const std::vector<Call*>& calls,
50+
const std::vector<CallRef*>& callRefs,
51+
Module* module,
52+
PassRunner* runner) {
53+
assert(funcs.size() > 0);
54+
auto* first = funcs[0];
55+
#ifndef NDEBUG
56+
for (auto* func : funcs) {
57+
assert(func->type == first->type);
58+
}
59+
#endif
60+
61+
// Check if none of the calls has a param with side effects that we cannot
62+
// remove (as if we can remove them, we will simply do that when we remove the
63+
// parameter). Note: flattening the IR beforehand can help here.
64+
bool callParamsAreValid =
65+
std::none_of(calls.begin(), calls.end(), [&](Call* call) {
66+
auto* operand = call->operands[index];
67+
return EffectAnalyzer(runner->options, *module, operand)
68+
.hasUnremovableSideEffects();
69+
});
70+
if (!callParamsAreValid) {
71+
return false;
72+
}
73+
74+
// The type must be valid for us to handle as a local (since we
75+
// replace the parameter with a local).
76+
// TODO: if there are no references at all, we can avoid creating a
77+
// local
78+
bool typeIsValid = TypeUpdating::canHandleAsLocal(first->getLocalType(index));
79+
if (!typeIsValid) {
80+
return false;
81+
}
82+
83+
// We can do it!
84+
85+
// Remove the parameter from the function. We must add a new local
86+
// for uses of the parameter, but cannot make it use the same index
87+
// (in general).
88+
auto paramsType = first->getParams();
89+
std::vector<Type> params(paramsType.begin(), paramsType.end());
90+
auto type = params[index];
91+
params.erase(params.begin() + index);
92+
// TODO: parallelize some of these loops?
93+
for (auto* func : funcs) {
94+
func->setParams(Type(params));
95+
96+
// It's cumbersome to adjust local names - TODO don't clear them?
97+
Builder::clearLocalNames(func);
98+
}
99+
std::vector<Index> newIndexes;
100+
for (auto* func : funcs) {
101+
newIndexes.push_back(Builder::addVar(func, type));
102+
}
103+
// Update local operations.
104+
struct LocalUpdater : public PostWalker<LocalUpdater> {
105+
Index removedIndex;
106+
Index newIndex;
107+
LocalUpdater(Function* func, Index removedIndex, Index newIndex)
108+
: removedIndex(removedIndex), newIndex(newIndex) {
109+
walk(func->body);
110+
}
111+
void visitLocalGet(LocalGet* curr) { updateIndex(curr->index); }
112+
void visitLocalSet(LocalSet* curr) { updateIndex(curr->index); }
113+
void updateIndex(Index& index) {
114+
if (index == removedIndex) {
115+
index = newIndex;
116+
} else if (index > removedIndex) {
117+
index--;
118+
}
119+
}
120+
};
121+
for (Index i = 0; i < funcs.size(); i++) {
122+
auto* func = funcs[i];
123+
if (!func->imported()) {
124+
LocalUpdater(funcs[i], index, newIndexes[i]);
125+
TypeUpdating::handleNonDefaultableLocals(func, *module);
126+
}
127+
}
128+
129+
// Remove the arguments from the calls.
130+
for (auto* call : calls) {
131+
call->operands.erase(call->operands.begin() + index);
132+
}
133+
for (auto* call : callRefs) {
134+
call->operands.erase(call->operands.begin() + index);
135+
}
136+
137+
return true;
138+
}
139+
140+
SortedVector removeParameters(const std::vector<Function*> funcs,
141+
SortedVector indexes,
142+
const std::vector<Call*>& calls,
143+
const std::vector<CallRef*>& callRefs,
144+
Module* module,
145+
PassRunner* runner) {
146+
if (indexes.empty()) {
147+
return {};
148+
}
149+
150+
assert(funcs.size() > 0);
151+
auto* first = funcs[0];
152+
#ifndef NDEBUG
153+
for (auto* func : funcs) {
154+
assert(func->type == first->type);
155+
}
156+
#endif
157+
158+
// Iterate downwards, as we may remove more than one, and going forwards would
159+
// alter the indexes after us.
160+
Index i = first->getNumParams() - 1;
161+
SortedVector removed;
162+
while (1) {
163+
if (indexes.has(i)) {
164+
if (removeParameter(funcs, i, calls, callRefs, module, runner)) {
165+
// Success!
166+
removed.insert(i);
167+
}
168+
}
169+
if (i == 0) {
170+
break;
171+
}
172+
i--;
173+
}
174+
return removed;
175+
}
176+
177+
} // namespace wasm::ParamUtils

0 commit comments

Comments
 (0)