/*
* Copyright 2016 WebAssembly Community Group participants
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
//
// Removes obviously unneeded code
//
#include <ir/block-utils.h>
#include <ir/effects.h>
#include <ir/literal-utils.h>
#include <ir/type-updating.h>
#include <ir/utils.h>
#include <pass.h>
#include <wasm-builder.h>
#include <wasm.h>
namespace wasm {
struct Vacuum : public WalkerPass<ExpressionStackWalker<Vacuum>> {
bool isFunctionParallel() override { return true; }
Pass* create() override { return new Vacuum; }
TypeUpdater typeUpdater;
Expression* replaceCurrent(Expression* expression) {
auto* old = getCurrent();
super::replaceCurrent(expression);
// also update the type updater
typeUpdater.noteReplacement(old, expression);
return expression;
}
void doWalkFunction(Function* func) {
typeUpdater.walk(func->body);
walk(func->body);
}
// Returns nullptr if curr is dead, curr if it must stay as is, or another
// node if it can be replaced. Takes into account:
// * The result may be used or unused.
// * The type may or may not matter (a drop can drop anything, for example).
Expression* optimize(Expression* curr, bool resultUsed, bool typeMatters) {
FeatureSet features = getModule()->features;
auto type = curr->type;
// An unreachable node must not be changed.
if (type == Type::unreachable) {
return curr;
}
// We iterate on possible replacements. If a replacement changes the type,
// stop and go back.
auto* prev = curr;
while (1) {
if (typeMatters && curr->type != type) {
return prev;
}
prev = curr;
switch (curr->_id) {
case Expression::Id::NopId:
return nullptr; // never needed
case Expression::Id::BlockId:
return curr; // not always needed, but handled in visitBlock()
case Expression::Id::IfId:
return curr; // not always needed, but handled in visitIf()
case Expression::Id::LoopId:
return curr; // not always needed, but handled in visitLoop()
case Expression::Id::DropId:
return curr; // not always needed, but handled in visitDrop()
case Expression::Id::TryId:
return curr; // not always needed, but handled in visitTry()
case Expression::Id::BreakId:
case Expression::Id::SwitchId:
case Expression::Id::BrOnExnId:
case Expression::Id::CallId:
case Expression::Id::CallIndirectId:
case Expression::Id::LocalSetId:
case Expression::Id::StoreId:
case Expression::Id::ReturnId:
case Expression::Id::GlobalSetId:
case Expression::Id::MemorySizeId:
case Expression::Id::MemoryGrowId:
case Expression::Id::UnreachableId:
return curr; // always needed
case Expression::Id::LoadId: {
// it is ok to remove a load if the result is not used, and it has no
// side effects (the load itself may trap, if we are not ignoring such
// things)
auto* load = curr->cast<Load>();
if (!resultUsed && !EffectAnalyzer(getPassOptions(), features, curr)
.hasSideEffects()) {
if (!typeMatters || load->ptr->type == type) {
return load->ptr;
}
}
return curr;
}
case Expression::Id::ConstId:
case Expression::Id::LocalGetId:
case Expression::Id::GlobalGetId: {
if (!resultUsed) {
return nullptr;
}
return curr;
}
case Expression::Id::UnaryId:
case Expression::Id::BinaryId:
case Expression::Id::SelectId: {
if (resultUsed) {
return curr; // used, keep it
}
// for unary, binary, and select, we need to check their arguments for
// side effects, as well as the node itself, as some unaries and
// binaries have implicit traps
if (auto* unary = curr->dynCast<Unary>()) {
EffectAnalyzer tester(getPassOptions(), features);
tester.visitUnary(unary);
if (tester.hasSideEffects()) {
return curr;
}
if (EffectAnalyzer(getPassOptions(), features, unary->value)
.hasSideEffects()) {
curr = unary->value;
continue;
} else {
return nullptr;
}
} else if (auto* binary = curr->dynCast<Binary>()) {
EffectAnalyzer tester(getPassOptions(), features);
tester.visitBinary(binary);
if (tester.hasSideEffects()) {
return curr;
}
if (EffectAnalyzer(getPassOptions(), features, binary->left)
.hasSideEffects()) {
if (EffectAnalyzer(getPassOptions(), features, binary->right)
.hasSideEffects()) {
return curr; // leave them
} else {
curr = binary->left;
continue;
}
} else {
if (EffectAnalyzer(getPassOptions(), features, binary->right)
.hasSideEffects()) {
curr = binary->right;
continue;
} else {
return nullptr;
}
}
} else {
// TODO: if two have side effects, we could replace the select with
// say an add?
auto* select = curr->cast<Select>();
if (EffectAnalyzer(getPassOptions(), features, select->ifTrue)
.hasSideEffects()) {
if (EffectAnalyzer(getPassOptions(), features, select->ifFalse)
.hasSideEffects()) {
return curr; // leave them
} else {
if (EffectAnalyzer(
getPassOptions(), features, select->condition)
.hasSideEffects()) {
return curr; // leave them
} else {
curr = select->ifTrue;
continue;
}
}
} else {
if (EffectAnalyzer(getPassOptions(), features, select->ifFalse)
.hasSideEffects()) {
if (EffectAnalyzer(
getPassOptions(), features, select->condition)
.hasSideEffects()) {
return curr; // leave them
} else {
curr = select->ifFalse;
continue;
}
} else {
if (EffectAnalyzer(
getPassOptions(), features, select->condition)
.hasSideEffects()) {
curr = select->condition;
continue;
} else {
return nullptr;
}
}
}
}
}
default:
return curr; // assume needed
}
}
}
void visitBlock(Block* curr) {
// compress out nops and other dead code
int skip = 0;
auto& list = curr->list;
size_t size = list.size();
for (size_t z = 0; z < size; z++) {
auto* child = list[z];
// The last element may be used.
bool used =
z == size - 1 && curr->type.isConcrete() &&
ExpressionAnalyzer::isResultUsed(expressionStack, getFunction());
auto* optimized = optimize(child, used, true);
if (!optimized) {
if (child->type.isConcrete()) {
// We can't just skip a final concrete element, even if it isn't used.
// Instead, replace it with something that's easy to optimize out (for
// example, code-folding can merge out identical zeros at the end of
// if arms).
optimized = LiteralUtils::makeZero(child->type, *getModule());
} else if (child->type == Type::unreachable) {
// Don't try to optimize out an unreachable child (dce can do that
// properly).
optimized = child;
}
}
if (!optimized) {
typeUpdater.noteRecursiveRemoval(child);
skip++;
} else {
if (optimized != child) {
typeUpdater.noteReplacement(child, optimized);
list[z] = optimized;
}
if (skip > 0) {
list[z - skip] = list[z];
list[z] = nullptr;
}
// if this is unreachable, the rest is dead code
if (list[z - skip]->type == Type::unreachable && z < size - 1) {
for (Index i = z - skip + 1; i < list.size(); i++) {
auto* remove = list[i];
if (remove) {
typeUpdater.noteRecursiveRemoval(remove);
}
}
list.resize(z - skip + 1);
typeUpdater.maybeUpdateTypeToUnreachable(curr);
skip = 0; // nothing more to do on the list
break;
}
}
}
if (skip > 0) {
list.resize(size - skip);
typeUpdater.maybeUpdateTypeToUnreachable(curr);
}
// the block may now be a trivial one that we can get rid of and just leave
// its contents
replaceCurrent(BlockUtils::simplifyToContents(curr, this));
}
void visitIf(If* curr) {
// if the condition is a constant, just apply it
// we can just return the ifTrue or ifFalse.
if (auto* value = curr->condition->dynCast<Const>()) {
Expression* child;
if (value->value.getInteger()) {
child = curr->ifTrue;
if (curr->ifFalse) {
typeUpdater.noteRecursiveRemoval(curr->ifFalse);
}
} else {
if (curr->ifFalse) {
child = curr->ifFalse;
typeUpdater.noteRecursiveRemoval(curr->ifTrue);
} else {
typeUpdater.noteRecursiveRemoval(curr);
ExpressionManipulator::nop(curr);
return;
}
}
replaceCurrent(child);
return;
}
// if the condition is unreachable, just return it
if (curr->condition->type == Type::unreachable) {
typeUpdater.noteRecursiveRemoval(curr->ifTrue);
if (curr->ifFalse) {
typeUpdater.noteRecursiveRemoval(curr->ifFalse);
}
replaceCurrent(curr->condition);
return;
}
// from here on, we can assume the condition executed
if (curr->ifFalse) {
if (curr->ifFalse->is<Nop>()) {
curr->ifFalse = nullptr;
} else if (curr->ifTrue->is<Nop>()) {
curr->ifTrue = curr->ifFalse;
curr->ifFalse = nullptr;
curr->condition =
Builder(*getModule()).makeUnary(EqZInt32, curr->condition);
} else if (curr->ifTrue->is<Drop>() && curr->ifFalse->is<Drop>()) {
// instead of dropping both sides, drop the if, if they are the same
// type
auto* left = curr->ifTrue->cast<Drop>()->value;
auto* right = curr->ifFalse->cast<Drop>()->value;
if (left->type == right->type) {
curr->ifTrue = left;
curr->ifFalse = right;
curr->finalize();
replaceCurrent(Builder(*getModule()).makeDrop(curr));
}
}
} else {
// no else
if (curr->ifTrue->is<Nop>()) {
// no nothing
replaceCurrent(Builder(*getModule()).makeDrop(curr->condition));
}
}
}
void visitLoop(Loop* curr) {
if (curr->body->is<Nop>()) {
ExpressionManipulator::nop(curr);
}
}
void visitDrop(Drop* curr) {
// optimize the dropped value, maybe leaving nothing
curr->value = optimize(curr->value, false, false);
if (curr->value == nullptr) {
ExpressionManipulator::nop(curr);
return;
}
// a drop of a tee is a set
if (auto* set = curr->value->dynCast<LocalSet>()) {
assert(set->isTee());
set->makeSet();
replaceCurrent(set);
return;
}
// if we are dropping a block's return value, we might be able to remove it
// entirely
if (auto* block = curr->value->dynCast<Block>()) {
auto* last = block->list.back();
// note that the last element may be concrete but not the block, if the
// block has an unreachable element in the middle, making the block
// unreachable despite later elements and in particular the last
if (last->type.isConcrete() && block->type == last->type) {
last = optimize(last, false, false);
if (!last) {
// we may be able to remove this, if there are no brs
bool canPop = true;
if (block->name.is()) {
BranchUtils::BranchSeeker seeker(block->name);
Expression* temp = block;
seeker.walk(temp);
if (seeker.found && seeker.valueType != Type::none) {
canPop = false;
}
}
if (canPop) {
block->list.back() = last;
block->list.pop_back();
block->type = Type::none;
// we don't need the drop anymore, let's see what we have left in
// the block
if (block->list.size() > 1) {
replaceCurrent(block);
} else if (block->list.size() == 1) {
replaceCurrent(block->list[0]);
} else {
ExpressionManipulator::nop(curr);
}
return;
}
}
}
}
// sink a drop into an arm of an if-else if the other arm ends in an
// unreachable, as it if is a branch, this can make that branch optimizable
// and more vaccuming possible
auto* iff = curr->value->dynCast<If>();
if (iff && iff->ifFalse && iff->type.isConcrete()) {
// reuse the drop in both cases
if (iff->ifTrue->type == Type::unreachable &&
iff->ifFalse->type.isConcrete()) {
curr->value = iff->ifFalse;
iff->ifFalse = curr;
iff->type = Type::none;
replaceCurrent(iff);
} else if (iff->ifFalse->type == Type::unreachable &&
iff->ifTrue->type.isConcrete()) {
curr->value = iff->ifTrue;
iff->ifTrue = curr;
iff->type = Type::none;
replaceCurrent(iff);
}
}
}
void visitTry(Try* curr) {
// If try's body does not throw, the whole try-catch can be replaced with
// the try's body.
if (!EffectAnalyzer(getPassOptions(), getModule()->features, curr->body)
.throws) {
replaceCurrent(curr->body);
typeUpdater.noteRecursiveRemoval(curr->catchBody);
}
}
void visitFunction(Function* curr) {
auto* optimized =
optimize(curr->body, curr->sig.results != Type::none, true);
if (optimized) {
curr->body = optimized;
} else {
ExpressionManipulator::nop(curr->body);
}
if (curr->sig.results == Type::none &&
!EffectAnalyzer(getPassOptions(), getModule()->features, curr->body)
.hasSideEffects()) {
ExpressionManipulator::nop(curr->body);
}
}
};
Pass* createVacuumPass() { return new Vacuum(); }
} // namespace wasm