/*
* 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.
*/
#include "Relooper.h"
#include <stdlib.h>
#include <string.h>
#include <list>
#include <stack>
#include <string>
#include "ir/branch-utils.h"
#include "ir/utils.h"
#include "parsing.h"
namespace CFG {
template<class T, class U>
static bool contains(const T& container, const U& contained) {
return !!container.count(contained);
}
#ifdef RELOOPER_DEBUG
static void PrintDebug(const char* Format, ...);
#define DebugDump(x, ...) Debugging::Dump(x, __VA_ARGS__)
#else
#define PrintDebug(x, ...)
#define DebugDump(x, ...)
#endif
// Rendering utilities
static wasm::Expression* HandleFollowupMultiples(wasm::Expression* Ret,
Shape* Parent,
RelooperBuilder& Builder,
bool InLoop) {
if (!Parent->Next) {
return Ret;
}
auto* Curr = Ret->dynCast<wasm::Block>();
if (!Curr || Curr->name.is()) {
Curr = Builder.makeBlock(Ret);
}
// for each multiple after us, we create a block target for breaks to reach
while (Parent->Next) {
auto* Multiple = Shape::IsMultiple(Parent->Next);
if (!Multiple) {
break;
}
for (auto& [Id, Body] : Multiple->InnerMap) {
Curr->name = Builder.getBlockBreakName(Id);
Curr->finalize(); // it may now be reachable, via a break
auto* Outer = Builder.makeBlock(Curr);
Outer->list.push_back(Body->Render(Builder, InLoop));
Outer->finalize(); // TODO: not really necessary
Curr = Outer;
}
Parent->Next = Parent->Next->Next;
}
// after the multiples is a simple or a loop, in both cases we must hit an
// entry block, and so this is the last one we need to take into account now
// (this is why we require that loops hit an entry).
if (Parent->Next) {
auto* Simple = Shape::IsSimple(Parent->Next);
if (Simple) {
// breaking on the next block's id takes us out, where we
// will reach its rendering
Curr->name = Builder.getBlockBreakName(Simple->Inner->Id);
} else {
// add one break target per entry for the loop
auto* Loop = Shape::IsLoop(Parent->Next);
assert(Loop);
assert(Loop->Entries.size() > 0);
if (Loop->Entries.size() == 1) {
Curr->name = Builder.getBlockBreakName((*Loop->Entries.begin())->Id);
} else {
for (auto* Entry : Loop->Entries) {
Curr->name = Builder.getBlockBreakName(Entry->Id);
Curr->finalize();
auto* Outer = Builder.makeBlock(Curr);
Outer->finalize(); // TODO: not really necessary
Curr = Outer;
}
}
}
}
Curr->finalize();
return Curr;
}
// Branch
Branch::Branch(wasm::Expression* ConditionInit, wasm::Expression* CodeInit)
: Condition(ConditionInit), Code(CodeInit) {}
Branch::Branch(std::vector<wasm::Index>&& ValuesInit,
wasm::Expression* CodeInit)
: Condition(nullptr), Code(CodeInit) {
if (ValuesInit.size() > 0) {
SwitchValues = std::make_unique<std::vector<wasm::Index>>(ValuesInit);
}
// otherwise, it is the default
}
wasm::Expression*
Branch::Render(RelooperBuilder& Builder, Block* Target, bool SetLabel) {
auto* Ret = Builder.makeBlock();
if (Code) {
Ret->list.push_back(Code);
}
if (SetLabel) {
Ret->list.push_back(Builder.makeSetLabel(Target->Id));
}
if (Type == Break) {
Ret->list.push_back(Builder.makeBlockBreak(Target->Id));
} else if (Type == Continue) {
assert(Ancestor);
Ret->list.push_back(Builder.makeShapeContinue(Ancestor->Id));
}
Ret->finalize();
return Ret;
}
// Block
Block::Block(Relooper* relooper,
wasm::Expression* CodeInit,
wasm::Expression* SwitchConditionInit)
: relooper(relooper), Code(CodeInit), SwitchCondition(SwitchConditionInit),
IsCheckedMultipleEntry(false) {}
void Block::AddBranchTo(Block* Target,
wasm::Expression* Condition,
wasm::Expression* Code) {
// cannot add more than one branch to the same target
assert(!contains(BranchesOut, Target));
BranchesOut[Target] = relooper->AddBranch(Condition, Code);
}
void Block::AddSwitchBranchTo(Block* Target,
std::vector<wasm::Index>&& Values,
wasm::Expression* Code) {
// cannot add more than one branch to the same target
assert(!contains(BranchesOut, Target));
BranchesOut[Target] = relooper->AddBranch(std::move(Values), Code);
}
wasm::Expression* Block::Render(RelooperBuilder& Builder, bool InLoop) {
auto* Ret = Builder.makeBlock();
if (IsCheckedMultipleEntry && InLoop) {
Ret->list.push_back(Builder.makeSetLabel(0));
}
if (Code) {
Ret->list.push_back(Code);
}
if (!ProcessedBranchesOut.size()) {
Ret->finalize();
return Ret;
}
// in some cases it is clear we can avoid setting label, see later
bool SetLabel = true;
// A setting of the label variable (label = x) is necessary if it can
// cause an impact. The main case is where we set label to x, then elsewhere
// we check if label is equal to that value, i.e., that label is an entry
// in a multiple block. We also need to reset the label when we enter
// that block, so that each setting is a one-time action: consider
//
// while (1) {
// if (check) label = 1;
// if (label == 1) { label = 0 }
// }
//
// (Note that this case is impossible due to fusing, but that is not
// material here.) So setting to 0 is important just to clear the 1 for
// future iterations.
// TODO: When inside a loop, if necessary clear the label variable
// once on the top, and never do settings that are in effect clears
// Fusing: If the next is a Multiple, we can fuse it with this block. Note
// that we must be the Inner of a Simple, so fusing means joining a Simple
// to a Multiple. What happens there is that all options in the Multiple
// *must* appear in the Simple (the Simple is the only one reaching the
// Multiple), so we can remove the Multiple and add its independent groups
// into the Simple's branches.
MultipleShape* Fused = Shape::IsMultiple(Parent->Next);
if (Fused) {
PrintDebug("Fusing Multiple to Simple\n", 0);
Parent->Next = Parent->Next->Next;
// When the Multiple has the same number of groups as we have branches,
// they will all be fused, so it is safe to not set the label at all.
// If a switch, then we can have multiple branches to the same target
// (in different table indexes), and so this check is not sufficient
// TODO: optimize
if (SetLabel && Fused->InnerMap.size() == ProcessedBranchesOut.size() &&
!SwitchCondition) {
SetLabel = false;
}
}
// The block we branch to without checking the condition, if none of the other
// conditions held.
Block* DefaultTarget = nullptr;
// Find the default target, the one without a condition
for (auto& [Target, Details] : ProcessedBranchesOut) {
if ((!SwitchCondition && !Details->Condition) ||
(SwitchCondition && !Details->SwitchValues)) {
assert(!DefaultTarget &&
"block has branches without a default (nullptr for the "
"condition)"); // Must be exactly one default // nullptr
DefaultTarget = Target;
}
}
// Since each Block* must* branch somewhere, this must be set
assert(DefaultTarget);
// root of the main part, that we are about to emit
wasm::Expression* Root = nullptr;
if (!SwitchCondition) {
// We'll emit a chain of if-elses
wasm::If* CurrIf = nullptr;
// we build an if, then add a child, then add a child to that, etc., so we
// must finalize them in reverse order
std::vector<wasm::If*> finalizeStack;
wasm::Expression* RemainingConditions = nullptr;
for (auto iter = ProcessedBranchesOut.begin();; iter++) {
Block* Target;
Branch* Details;
if (iter != ProcessedBranchesOut.end()) {
Target = iter->first;
if (Target == DefaultTarget) {
continue; // done at the end
}
Details = iter->second;
// must have a condition if this is not the default target
assert(Details->Condition);
} else {
Target = DefaultTarget;
Details = ProcessedBranchesOut[DefaultTarget];
}
bool SetCurrLabel = SetLabel && Target->IsCheckedMultipleEntry;
bool HasFusedContent = Fused && contains(Fused->InnerMap, Target->Id);
if (HasFusedContent) {
assert(Details->Type == Branch::Break);
Details->Type = Branch::Direct;
}
wasm::Expression* CurrContent = nullptr;
bool IsDefault = iter == ProcessedBranchesOut.end();
if (SetCurrLabel || Details->Type != Branch::Direct || HasFusedContent ||
Details->Code) {
CurrContent = Details->Render(Builder, Target, SetCurrLabel);
if (HasFusedContent) {
CurrContent = Builder.blockify(
CurrContent,
Fused->InnerMap.find(Target->Id)->second->Render(Builder, InLoop));
}
}
// If there is nothing to show in this branch, omit the condition
if (CurrContent) {
if (IsDefault) {
wasm::Expression* Now;
if (RemainingConditions) {
Now = Builder.makeIf(RemainingConditions, CurrContent);
finalizeStack.push_back(Now->cast<wasm::If>());
} else {
Now = CurrContent;
}
if (!CurrIf) {
assert(!Root);
Root = Now;
} else {
CurrIf->ifFalse = Now;
CurrIf->finalize();
}
} else {
auto* Now = Builder.makeIf(Details->Condition, CurrContent);
finalizeStack.push_back(Now);
if (!CurrIf) {
assert(!Root);
Root = CurrIf = Now;
} else {
CurrIf->ifFalse = Now;
CurrIf->finalize();
CurrIf = Now;
}
}
} else {
auto* Now = Builder.makeUnary(wasm::EqZInt32, Details->Condition);
if (RemainingConditions) {
RemainingConditions =
Builder.makeBinary(wasm::AndInt32, RemainingConditions, Now);
} else {
RemainingConditions = Now;
}
}
if (IsDefault) {
break;
}
}
// finalize the if-chains
while (finalizeStack.size() > 0) {
wasm::If* curr = finalizeStack.back();
finalizeStack.pop_back();
curr->finalize();
}
} else {
// Emit a switch
auto Base = std::string("switch$") + std::to_string(Id);
auto SwitchDefault = wasm::Name(Base + "$default");
auto SwitchLeave = wasm::Name(Base + "$leave");
std::map<Block*, wasm::Name> BlockNameMap;
auto* Outer = Builder.makeBlock();
auto* Inner = Outer;
std::vector<wasm::Name> Table;
for (auto& [Target, Details] : ProcessedBranchesOut) {
wasm::Name CurrName;
if (Details->SwitchValues) {
CurrName = wasm::Name(Base + "$case$" + std::to_string(Target->Id));
} else {
CurrName = SwitchDefault;
}
// generate the content for this block
bool SetCurrLabel = SetLabel && Target->IsCheckedMultipleEntry;
bool HasFusedContent = Fused && contains(Fused->InnerMap, Target->Id);
if (HasFusedContent) {
assert(Details->Type == Branch::Break);
Details->Type = Branch::Direct;
}
wasm::Expression* CurrContent = nullptr;
if (SetCurrLabel || Details->Type != Branch::Direct || HasFusedContent ||
Details->Code) {
CurrContent = Details->Render(Builder, Target, SetCurrLabel);
if (HasFusedContent) {
CurrContent = Builder.blockify(
CurrContent,
Fused->InnerMap.find(Target->Id)->second->Render(Builder, InLoop));
}
}
// generate a block to branch to, if we have content
if (CurrContent) {
auto* NextOuter = Builder.makeBlock();
NextOuter->list.push_back(Outer);
// breaking on Outer leads to the content in NextOuter
Outer->name = CurrName;
NextOuter->list.push_back(CurrContent);
// if this is not a dead end, also need to break to the outside this is
// both an optimization, and avoids incorrectness as adding a break in
// unreachable code can make a place look reachable that isn't
if (CurrContent->type != wasm::Type::unreachable) {
NextOuter->list.push_back(Builder.makeBreak(SwitchLeave));
}
// prepare for more nesting
Outer = NextOuter;
} else {
CurrName = SwitchLeave; // just go out straight from the table
if (!Details->SwitchValues) {
// this is the default, and it has no content. So make the default be
// the leave
for (auto& Value : Table) {
if (Value == SwitchDefault) {
Value = SwitchLeave;
}
}
SwitchDefault = SwitchLeave;
}
}
if (Details->SwitchValues) {
for (auto Value : *Details->SwitchValues) {
while (Table.size() <= Value) {
Table.push_back(SwitchDefault);
}
Table[Value] = CurrName;
}
}
}
// finish up the whole pattern
Outer->name = SwitchLeave;
Inner->list.push_back(
Builder.makeSwitch(Table, SwitchDefault, SwitchCondition));
Root = Outer;
}
if (Root) {
Ret->list.push_back(Root);
}
Ret->finalize();
return Ret;
}
// SimpleShape
wasm::Expression* SimpleShape::Render(RelooperBuilder& Builder, bool InLoop) {
auto* Ret = Inner->Render(Builder, InLoop);
Ret = HandleFollowupMultiples(Ret, this, Builder, InLoop);
if (Next) {
Ret = Builder.makeSequence(Ret, Next->Render(Builder, InLoop));
}
return Ret;
}
// MultipleShape
wasm::Expression* MultipleShape::Render(RelooperBuilder& Builder, bool InLoop) {
// TODO: consider switch
// emit an if-else chain
wasm::If* FirstIf = nullptr;
wasm::If* CurrIf = nullptr;
std::vector<wasm::If*> finalizeStack;
for (auto& [Id, Body] : InnerMap) {
auto* Now =
Builder.makeIf(Builder.makeCheckLabel(Id), Body->Render(Builder, InLoop));
finalizeStack.push_back(Now);
if (!CurrIf) {
FirstIf = CurrIf = Now;
} else {
CurrIf->ifFalse = Now;
CurrIf->finalize();
CurrIf = Now;
}
}
while (finalizeStack.size() > 0) {
wasm::If* curr = finalizeStack.back();
finalizeStack.pop_back();
curr->finalize();
}
wasm::Expression* Ret = Builder.makeBlock(FirstIf);
Ret = HandleFollowupMultiples(Ret, this, Builder, InLoop);
if (Next) {
Ret = Builder.makeSequence(Ret, Next->Render(Builder, InLoop));
}
return Ret;
}
// LoopShape
wasm::Expression* LoopShape::Render(RelooperBuilder& Builder, bool InLoop) {
wasm::Expression* Ret = Builder.makeLoop(Builder.getShapeContinueName(Id),
Inner->Render(Builder, true));
Ret = HandleFollowupMultiples(Ret, this, Builder, InLoop);
if (Next) {
Ret = Builder.makeSequence(Ret, Next->Render(Builder, InLoop));
}
return Ret;
}
// Relooper
Relooper::Relooper(wasm::Module* ModuleInit)
: Module(ModuleInit), Root(nullptr), MinSize(false), BlockIdCounter(1),
ShapeIdCounter(0) { // block ID 0 is reserved for clearings
}
Block* Relooper::AddBlock(wasm::Expression* CodeInit,
wasm::Expression* SwitchConditionInit) {
auto block = std::make_unique<Block>(this, CodeInit, SwitchConditionInit);
block->Id = BlockIdCounter++;
auto* blockPtr = block.get();
Blocks.push_back(std::move(block));
return blockPtr;
}
Branch* Relooper::AddBranch(wasm::Expression* ConditionInit,
wasm::Expression* CodeInit) {
auto branch = std::make_unique<Branch>(ConditionInit, CodeInit);
auto* branchPtr = branch.get();
Branches.push_back(std::move(branch));
return branchPtr;
}
Branch* Relooper::AddBranch(std::vector<wasm::Index>&& ValuesInit,
wasm::Expression* CodeInit) {
auto branch = std::make_unique<Branch>(std::move(ValuesInit), CodeInit);
auto* branchPtr = branch.get();
Branches.push_back(std::move(branch));
return branchPtr;
}
SimpleShape* Relooper::AddSimpleShape() {
auto shape = std::make_unique<SimpleShape>();
shape->Id = ShapeIdCounter++;
auto* shapePtr = shape.get();
Shapes.push_back(std::move(shape));
return shapePtr;
}
MultipleShape* Relooper::AddMultipleShape() {
auto shape = std::make_unique<MultipleShape>();
shape->Id = ShapeIdCounter++;
auto* shapePtr = shape.get();
Shapes.push_back(std::move(shape));
return shapePtr;
}
LoopShape* Relooper::AddLoopShape() {
auto shape = std::make_unique<LoopShape>();
shape->Id = ShapeIdCounter++;
auto* shapePtr = shape.get();
Shapes.push_back(std::move(shape));
return shapePtr;
}
namespace {
using BlockList = std::list<Block*>;
struct RelooperRecursor {
Relooper* Parent;
RelooperRecursor(Relooper* ParentInit) : Parent(ParentInit) {}
};
struct Liveness : public RelooperRecursor {
Liveness(Relooper* Parent) : RelooperRecursor(Parent) {}
BlockSet Live;
void FindLive(Block* Root) {
BlockList ToInvestigate;
ToInvestigate.push_back(Root);
while (ToInvestigate.size() > 0) {
Block* Curr = ToInvestigate.front();
ToInvestigate.pop_front();
if (contains(Live, Curr)) {
continue;
}
Live.insert(Curr);
for (auto& iter : Curr->BranchesOut) {
ToInvestigate.push_back(iter.first);
}
}
}
};
using BranchBlock = std::pair<Branch*, Block*>;
struct Optimizer : public RelooperRecursor {
Block* Entry;
Optimizer(Relooper* Parent, Block* EntryInit)
: RelooperRecursor(Parent), Entry(EntryInit) {
// TODO: there are likely some rare but possible O(N^2) cases with this
// looping
bool More = true;
#if RELOOPER_OPTIMIZER_DEBUG
std::cout << "pre-optimize\n";
for (auto* Block : Parent->Blocks) {
DebugDump(Block, "pre-block");
}
#endif
// First, run one-time preparatory passes.
CanonicalizeCode();
// Loop over passes that allow further reduction.
while (More) {
More = false;
More = SkipEmptyBlocks() || More;
More = MergeEquivalentBranches() || More;
More = UnSwitch() || More;
More = MergeConsecutiveBlocks() || More;
// TODO: Merge identical blocks. This would avoid taking into account
// their position / how they are reached, which means that the merging may
// add overhead, so we do it carefully:
// * Merging a large-enough block is good for size, and we do it
// in we are in MinSize mode, which means we can tolerate slightly
// slower throughput.
// TODO: Fuse a non-empty block with a single successor.
}
// Finally, run one-time final passes.
// TODO
#if RELOOPER_OPTIMIZER_DEBUG
std::cout << "post-optimize\n";
for (auto* Block : Parent->Blocks) {
DebugDump(Block, "post-block");
}
#endif
}
// We will be performing code comparisons, so do some basic canonicalization
// to avoid things being unequal for silly reasons.
void CanonicalizeCode() {
for (auto& Block : Parent->Blocks) {
Block->Code = Canonicalize(Block->Code);
for (auto& [_, Branch] : Block->BranchesOut) {
if (Branch->Code) {
Branch->Code = Canonicalize(Branch->Code);
}
}
}
}
// If a branch goes to an empty block which has one target,
// and there is no phi or switch to worry us, just skip through.
bool SkipEmptyBlocks() {
bool Worked = false;
for (auto& CurrBlock : Parent->Blocks) {
// Generate a new set of branches out TODO optimize
BlockBranchMap NewBranchesOut;
for (auto& iter : CurrBlock->BranchesOut) {
auto* Next = iter.first;
auto* NextBranch = iter.second;
auto* First = Next;
auto* Replacement = First;
#if RELOOPER_OPTIMIZER_DEBUG
std::cout << " maybeskip from " << Block->Id << " to next=" << Next->Id
<< '\n';
#endif
std::unordered_set<decltype(Replacement)> Seen;
while (1) {
if (IsEmpty(Next) && Next->BranchesOut.size() == 1) {
auto iter = Next->BranchesOut.begin();
Block* NextNext = iter->first;
Branch* NextNextBranch = iter->second;
assert(!NextNextBranch->Condition && !NextNextBranch->SwitchValues);
if (!NextNextBranch->Code) { // TODO: handle extra code too
// We can skip through!
Next = Replacement = NextNext;
// If we've already seen this, stop - it's an infinite loop of
// empty blocks we can skip through.
if (!Seen.emplace(Replacement).second) {
// Stop here. Note that if we started from X and ended up with X
// once more, then Replacement == First and so lower down we
// will not report that we did any work, avoiding an infinite
// loop due to always thinking there is more work to do.
break;
} else {
// Otherwise, keep going.
continue;
}
}
}
break;
}
if (Replacement != First) {
#if RELOOPER_OPTIMIZER_DEBUG
std::cout << " skip to replacement! " << CurrBlock->Id << " -> "
<< First->Id << " -> " << Replacement->Id << '\n';
#endif
Worked = true;
}
// Add a branch to the target (which may be the unchanged original) in
// the set of new branches. If it's a replacement, it may collide, and
// we need to merge.
if (NewBranchesOut.count(Replacement)) {
#if RELOOPER_OPTIMIZER_DEBUG
std::cout << " merge\n";
#endif
MergeBranchInto(NextBranch, NewBranchesOut[Replacement]);
} else {
NewBranchesOut[Replacement] = NextBranch;
}
}
CurrBlock->BranchesOut.swap(NewBranchesOut);
}
return Worked;
}
// Our IR has one Branch from each block to one of its targets, so there
// is nothing to reduce there, but different targets may in fact be
// equivalent in their *contents*.
bool MergeEquivalentBranches() {
bool Worked = false;
for (auto& ParentBlock : Parent->Blocks) {
#if RELOOPER_OPTIMIZER_DEBUG
std::cout << "at parent " << ParentBlock->Id << '\n';
#endif
if (ParentBlock->BranchesOut.size() >= 2) {
std::unordered_map<size_t, std::vector<BranchBlock>> HashedBranchesOut;
std::vector<Block*> BlocksToErase;
for (auto& [CurrBlock, CurrBranch] : ParentBlock->BranchesOut) {
#if RELOOPER_OPTIMIZER_DEBUG
std::cout << " consider child " << CurrBlock->Id << '\n';
#endif
if (CurrBranch->Code) {
// We can't merge code; ignore
continue;
}
auto HashValue = Hash(CurrBlock);
auto& HashedSiblings = HashedBranchesOut[HashValue];
// Check if we are equivalent to any of them - if so, merge us.
bool Merged = false;
for (auto& [SiblingBranch, SiblingBlock] : HashedSiblings) {
if (HaveEquivalentContents(CurrBlock, SiblingBlock)) {
#if RELOOPER_OPTIMIZER_DEBUG
std::cout << " equiv! to " << SiblingBlock->Id << '\n';
#endif
MergeBranchInto(CurrBranch, SiblingBranch);
BlocksToErase.push_back(CurrBlock);
Merged = true;
Worked = true;
}
#if RELOOPER_OPTIMIZER_DEBUG
else {
std::cout << " same hash, but not equiv to "
<< SiblingBlock->Id << '\n';
}
#endif
}
if (!Merged) {
HashedSiblings.emplace_back(CurrBranch, CurrBlock);
}
}
for (auto* Curr : BlocksToErase) {
ParentBlock->BranchesOut.erase(Curr);
}
}
}
return Worked;
}
// Merge consecutive blocks, that is, A -> B where no other branches go to B.
// In that case we are guaranteed to not increase code size.
bool MergeConsecutiveBlocks() {
bool Worked = false;
// First, count predecessors.
std::map<Block*, size_t> NumPredecessors;
for (auto& CurrBlock : Parent->Blocks) {
for (auto& iter : CurrBlock->BranchesOut) {
auto* NextBlock = iter.first;
NumPredecessors[NextBlock]++;
}
}
NumPredecessors[Entry]++;
for (auto& CurrBlock : Parent->Blocks) {
if (CurrBlock->BranchesOut.size() == 1) {
auto iter = CurrBlock->BranchesOut.begin();
auto* NextBlock = iter->first;
auto* NextBranch = iter->second;
assert(NumPredecessors[NextBlock] > 0);
if (NextBlock != CurrBlock.get() && NumPredecessors[NextBlock] == 1) {
// Good to merge!
wasm::Builder Builder(*Parent->Module);
// Merge in code on the branch as well, if any.
if (NextBranch->Code) {
CurrBlock->Code =
Builder.makeSequence(CurrBlock->Code, NextBranch->Code);
}
CurrBlock->Code =
Builder.makeSequence(CurrBlock->Code, NextBlock->Code);
// Use the next block's branching behavior
CurrBlock->BranchesOut.swap(NextBlock->BranchesOut);
NextBlock->BranchesOut.clear();
CurrBlock->SwitchCondition = NextBlock->SwitchCondition;
// The next block now has no predecessors.
NumPredecessors[NextBlock] = 0;
Worked = true;
}
}
}
return Worked;
}
// Removes unneeded switches - if only one branch is left, the default, then
// no switch is needed.
bool UnSwitch() {
bool Worked = false;
for (auto& ParentBlock : Parent->Blocks) {
#if RELOOPER_OPTIMIZER_DEBUG
std::cout << "un-switching at " << ParentBlock->Id << ' '
<< !!ParentBlock->SwitchCondition << ' '
<< ParentBlock->BranchesOut.size() << '\n';
#endif
if (ParentBlock->SwitchCondition) {
if (ParentBlock->BranchesOut.size() <= 1) {
#if RELOOPER_OPTIMIZER_DEBUG
std::cout << " un-switching!: " << ParentBlock->Id << '\n';
#endif
ParentBlock->SwitchCondition = nullptr;
if (!ParentBlock->BranchesOut.empty()) {
assert(!ParentBlock->BranchesOut.begin()->second->SwitchValues);
}
Worked = true;
}
} else {
// If the block has no switch, the branches must not as well.
#ifndef NDEBUG
for (auto& [_, CurrBranch] : ParentBlock->BranchesOut) {
assert(!CurrBranch->SwitchValues);
}
#endif
}
}
return Worked;
}
private:
wasm::Expression* Canonicalize(wasm::Expression* Curr) {
wasm::Builder Builder(*Parent->Module);
// Our preferred form is a block with no name and a flat list
// with Nops removed, and extra Unreachables removed as well.
// If the block would contain one item, return just the item.
wasm::Block* Outer = Curr->dynCast<wasm::Block>();
if (!Outer) {
Outer = Builder.makeBlock(Curr);
} else if (Outer->name.is()) {
// Perhaps the name can be removed.
if (!wasm::BranchUtils::BranchSeeker::has(Outer, Outer->name)) {
Outer->name = wasm::Name();
} else {
Outer = Builder.makeBlock(Curr);
}
}
Flatten(Outer);
if (Outer->list.size() == 1) {
return Outer->list[0];
} else {
return Outer;
}
}
void Flatten(wasm::Block* Outer) {
wasm::ExpressionList NewList(Parent->Module->allocator);
bool SeenUnreachableType = false;
auto Add = [&](wasm::Expression* Curr) {
if (Curr->is<wasm::Nop>()) {
// Do nothing with it.
return;
} else if (Curr->is<wasm::Unreachable>()) {
// If we already saw an unreachable-typed item, emit no
// Unreachable nodes after it.
if (SeenUnreachableType) {
return;
}
}
NewList.push_back(Curr);
if (Curr->type == wasm::Type::unreachable) {
SeenUnreachableType = true;
}
};
std::function<void(wasm::Block*)> FlattenIntoNewList =
[&](wasm::Block* Curr) {
assert(!Curr->name.is());
for (auto* Item : Curr->list) {
if (auto* Block = Item->dynCast<wasm::Block>()) {
if (Block->name.is()) {
// Leave it whole, it's not a trivial block.
Add(Block);
} else {
FlattenIntoNewList(Block);
}
} else {
// A random item.
Add(Item);
}
}
// All the items have been moved out.
Curr->list.clear();
};
FlattenIntoNewList(Outer);
assert(Outer->list.empty());
Outer->list.swap(NewList);
}
bool IsEmpty(Block* Curr) {
if (Curr->SwitchCondition) {
// This is non-trivial, so treat it as a non-empty block.
return false;
}
return IsEmpty(Curr->Code);
}
bool IsEmpty(wasm::Expression* Code) {
if (Code->is<wasm::Nop>()) {
return true; // a nop
}
if (auto* WasmBlock = Code->dynCast<wasm::Block>()) {
for (auto* Item : WasmBlock->list) {
if (!IsEmpty(Item)) {
return false;
}
}
return true; // block with no non-empty contents
}
return false;
}
// Checks functional equivalence, namely: the Code and SwitchCondition.
// We also check the branches out, *non-recursively*: that is, we check
// that they are literally identical, not that they can be computed to
// be equivalent.
bool HaveEquivalentContents(Block* A, Block* B) {
if (!IsPossibleCodeEquivalent(A->SwitchCondition, B->SwitchCondition)) {
return false;
}
if (!IsCodeEquivalent(A->Code, B->Code)) {
return false;
}
if (A->BranchesOut.size() != B->BranchesOut.size()) {
return false;
}
for (auto& [ABlock, ABranch] : A->BranchesOut) {
if (B->BranchesOut.count(ABlock) == 0) {
return false;
}
auto* BBranch = B->BranchesOut[ABlock];
if (!IsPossibleCodeEquivalent(ABranch->Condition, BBranch->Condition)) {
return false;
}
if (!IsPossibleUniquePtrEquivalent(ABranch->SwitchValues,
BBranch->SwitchValues)) {
return false;
}
if (!IsPossibleCodeEquivalent(ABranch->Code, BBranch->Code)) {
return false;
}
}
return true;
}
// Checks if values referred to by pointers are identical, allowing the code
// to also be nullptr
template<typename T>
static bool IsPossibleUniquePtrEquivalent(std::unique_ptr<T>& A,
std::unique_ptr<T>& B) {
if (A == B) {
return true;
}
if (!A || !B) {
return false;
}
return *A == *B;
}
// Checks if code is equivalent, allowing the code to also be nullptr
static bool IsPossibleCodeEquivalent(wasm::Expression* A,
wasm::Expression* B) {
if (A == B) {
return true;
}
if (!A || !B) {
return false;
}
return IsCodeEquivalent(A, B);
}
static bool IsCodeEquivalent(wasm::Expression* A, wasm::Expression* B) {
return wasm::ExpressionAnalyzer::equal(A, B);
}
// Merges one branch into another. Valid under the assumption that the
// blocks they reach are identical, and so one branch is enough for both
// with a unified condition.
// Only one is allowed to have code, as the code may have side effects,
// and we don't have a way to order or resolve those, unless the code
// is equivalent.
void MergeBranchInto(Branch* Curr, Branch* Into) {
assert(Curr != Into);
if (Curr->SwitchValues) {
if (!Into->SwitchValues) {
assert(!Into->Condition);
// Merging into the already-default, nothing to do.
} else {
Into->SwitchValues->insert(Into->SwitchValues->end(),
Curr->SwitchValues->begin(),
Curr->SwitchValues->end());
}
} else {
if (!Curr->Condition) {
// This is now the new default. Whether Into has a condition
// or switch values, remove them all to make us the default.
Into->Condition = nullptr;
Into->SwitchValues.reset();
} else if (!Into->Condition) {
// Nothing to do, already the default.
} else {
assert(!Into->SwitchValues);
// Merge them, checking both.
Into->Condition =
wasm::Builder(*Parent->Module)
.makeBinary(wasm::OrInt32, Into->Condition, Curr->Condition);
}
}
if (!Curr->Code) {
// No code to merge in.
} else if (!Into->Code) {
// Just use the code being merged in.
Into->Code = Curr->Code;
} else {
assert(IsCodeEquivalent(Into->Code, Curr->Code));
// Keep the code already there, either is fine.
}
}
// Hashes the direct block contents, but not Relooper internals
// (like Shapes). Only partially hashes the branches out, no
// recursion: hashes the branch infos, looks at raw pointers
// for the blocks.
size_t Hash(Block* Curr) {
auto digest = wasm::ExpressionAnalyzer::hash(Curr->Code);
wasm::rehash(digest, uint8_t(1));
if (Curr->SwitchCondition) {
wasm::hash_combine(digest,
wasm::ExpressionAnalyzer::hash(Curr->SwitchCondition));
}
wasm::rehash(digest, uint8_t(2));
for (auto& [CurrBlock, CurrBranch] : Curr->BranchesOut) {
// Hash the Block* as a pointer TODO: full hash?
wasm::rehash(digest, reinterpret_cast<size_t>(CurrBlock));
// Hash the Branch info properly
wasm::hash_combine(digest, Hash(CurrBranch));
}
return digest;
}
// Hashes the direct block contents, but not Relooper internals
// (like Shapes).
size_t Hash(Branch* Curr) {
auto digest = wasm::hash(0);
if (Curr->SwitchValues) {
for (auto i : *Curr->SwitchValues) {
wasm::rehash(digest, i); // TODO hash i
}
} else {
if (Curr->Condition) {
wasm::hash_combine(digest,
wasm::ExpressionAnalyzer::hash(Curr->Condition));
}
}
wasm::rehash(digest, uint8_t(1));
if (Curr->Code) {
wasm::hash_combine(digest, wasm::ExpressionAnalyzer::hash(Curr->Code));
}
return digest;
}
};
} // namespace
void Relooper::Calculate(Block* Entry) {
// Optimize.
Optimizer(this, Entry);
// Find live blocks.
Liveness Live(this);
Live.FindLive(Entry);
// Add incoming branches from live blocks, ignoring dead code
for (unsigned i = 0; i < Blocks.size(); i++) {
Block* Curr = Blocks[i].get();
if (!contains(Live.Live, Curr)) {
continue;
}
for (auto& [CurrBlock, _] : Curr->BranchesOut) {
CurrBlock->BranchesIn.insert(Curr);
}
}
// Recursively process the graph
struct Analyzer : public RelooperRecursor {
Analyzer(Relooper* Parent) : RelooperRecursor(Parent) {}
// Create a list of entries from a block. If LimitTo is provided, only
// results in that set will appear
void GetBlocksOut(Block* Source,
BlockSet& Entries,
BlockSet* LimitTo = nullptr) {
for (auto& [CurrBlock, _] : Source->BranchesOut) {
if (!LimitTo || contains(*LimitTo, CurrBlock)) {
Entries.insert(CurrBlock);
}
}
}
// Converts/processes all branchings to a specific target
void Solipsize(Block* Target,
Branch::FlowType Type,
Shape* Ancestor,
BlockSet& From) {
PrintDebug("Solipsizing branches into %d\n", Target->Id);
DebugDump(From, " relevant to solipsize: ");
for (auto iter = Target->BranchesIn.begin();
iter != Target->BranchesIn.end();) {
Block* Prior = *iter;
if (!contains(From, Prior)) {
iter++;
continue;
}
Branch* PriorOut = Prior->BranchesOut[Target];
PriorOut->Ancestor = Ancestor;
PriorOut->Type = Type;
iter++; // carefully increment iter before erasing
Target->BranchesIn.erase(Prior);
Target->ProcessedBranchesIn.insert(Prior);
Prior->BranchesOut.erase(Target);
Prior->ProcessedBranchesOut[Target] = PriorOut;
PrintDebug(" eliminated branch from %d\n", Prior->Id);
}
}
Shape* MakeSimple(BlockSet& Blocks, Block* Inner, BlockSet& NextEntries) {
PrintDebug("creating simple block with block #%d\n", Inner->Id);
SimpleShape* Simple = Parent->AddSimpleShape();
Simple->Inner = Inner;
Inner->Parent = Simple;
if (Blocks.size() > 1) {
Blocks.erase(Inner);
GetBlocksOut(Inner, NextEntries, &Blocks);
BlockSet JustInner;
JustInner.insert(Inner);
for (auto* Next : NextEntries) {
Solipsize(Next, Branch::Break, Simple, JustInner);
}
}
return Simple;
}
Shape*
MakeLoop(BlockSet& Blocks, BlockSet& Entries, BlockSet& NextEntries) {
// Find the inner blocks in this loop. Proceed backwards from the entries
// until you reach a seen block, collecting as you go.
BlockSet InnerBlocks;
BlockSet Queue = Entries;
while (Queue.size() > 0) {
Block* Curr = *(Queue.begin());
Queue.erase(Queue.begin());
if (!contains(InnerBlocks, Curr)) {
// This element is new, mark it as inner and remove from outer
InnerBlocks.insert(Curr);
Blocks.erase(Curr);
// Add the elements prior to it
for (auto* Prev : Curr->BranchesIn) {
Queue.insert(Prev);
}
#if 0
// Add elements it leads to, if they are dead ends. There is no reason not to hoist dead ends
// into loops, as it can avoid multiple entries after the loop
for (auto iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) {
Block* Target = iter->first;
if (Target->BranchesIn.size() <= 1 && Target->BranchesOut.size() == 0) {
Queue.insert(Target);
}
}
#endif
}
}
assert(InnerBlocks.size() > 0);
for (auto* Curr : InnerBlocks) {
for (auto& [Possible, _] : Curr->BranchesOut) {
if (!contains(InnerBlocks, Possible)) {
NextEntries.insert(Possible);
}
}
}
#if 0
// We can avoid multiple next entries by hoisting them into the loop.
if (NextEntries.size() > 1) {
BlockBlockSetMap IndependentGroups;
FindIndependentGroups(NextEntries, IndependentGroups, &InnerBlocks);
while (IndependentGroups.size() > 0 && NextEntries.size() > 1) {
Block* Min = nullptr;
int MinSize = 0;
for (auto iter = IndependentGroups.begin(); iter != IndependentGroups.end(); iter++) {
Block* Entry = iter->first;
BlockSet &Blocks = iter->second;
if (!Min || Blocks.size() < MinSize) { // TODO: code size, not # of blocks
Min = Entry;
MinSize = Blocks.size();
}
}
// check how many new entries this would cause
BlockSet &Hoisted = IndependentGroups[Min];
bool abort = false;
for (auto iter = Hoisted.begin(); iter != Hoisted.end() && !abort; iter++) {
Block* Curr = *iter;
for (auto iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) {
Block* Target = iter->first;
if (!contains(Hoisted, Target) && !contains(NextEntries, Target)) {
// abort this hoisting
abort = true;
break;
}
}
}
if (abort) {
IndependentGroups.erase(Min);
continue;
}
// hoist this entry
PrintDebug("hoisting %d into loop\n", Min->Id);
NextEntries.erase(Min);
for (auto iter = Hoisted.begin(); iter != Hoisted.end(); iter++) {
Block* Curr = *iter;
InnerBlocks.insert(Curr);
Blocks.erase(Curr);
}
IndependentGroups.erase(Min);
}
}
#endif
PrintDebug("creating loop block:\n", 0);
DebugDump(InnerBlocks, " inner blocks:");
DebugDump(Entries, " inner entries:");
DebugDump(Blocks, " outer blocks:");
DebugDump(NextEntries, " outer entries:");
LoopShape* Loop = Parent->AddLoopShape();
// Solipsize the loop, replacing with break/continue and marking branches
// as Processed (will not affect later calculations) A. Branches to the
// loop entries become a continue to this shape
for (auto* Entry : Entries) {
Solipsize(Entry, Branch::Continue, Loop, InnerBlocks);
}
// B. Branches to outside the loop (a next entry) become breaks on this
// shape
for (auto* Next : NextEntries) {
Solipsize(Next, Branch::Break, Loop, InnerBlocks);
}
// Finish up
Shape* Inner = Process(InnerBlocks, Entries);
Loop->Inner = Inner;
Loop->Entries = Entries;
return Loop;
}
// For each entry, find the independent group reachable by it. The
// independent group is the entry itself, plus all the blocks it can reach
// that cannot be directly reached by another entry. Note that we ignore
// directly reaching the entry itself by another entry.
// @param Ignore - previous blocks that are irrelevant
void FindIndependentGroups(BlockSet& Entries,
BlockBlockSetMap& IndependentGroups,
BlockSet* Ignore = nullptr) {
using BlockBlockMap = std::map<Block*, Block*>;
struct HelperClass {
BlockBlockSetMap& IndependentGroups;
// For each block, which entry it belongs to. We have reached it from
// there.
BlockBlockMap Ownership;
HelperClass(BlockBlockSetMap& IndependentGroupsInit)
: IndependentGroups(IndependentGroupsInit) {}
void InvalidateWithChildren(Block* New) { // TODO: rename New
// Being in the list means you need to be invalidated
BlockList ToInvalidate;
ToInvalidate.push_back(New);
while (ToInvalidate.size() > 0) {
Block* Invalidatee = ToInvalidate.front();
ToInvalidate.pop_front();
Block* Owner = Ownership[Invalidatee];
// Owner may have been invalidated, do not add to IndependentGroups!
if (contains(IndependentGroups, Owner)) {
IndependentGroups[Owner].erase(Invalidatee);
}
// may have been seen before and invalidated already
if (Ownership[Invalidatee]) {
Ownership[Invalidatee] = nullptr;
for (auto& [Target, _] : Invalidatee->BranchesOut) {
auto Known = Ownership.find(Target);
if (Known != Ownership.end()) {
Block* TargetOwner = Known->second;
if (TargetOwner) {
ToInvalidate.push_back(Target);
}
}
}
}
}
}
};
HelperClass Helper(IndependentGroups);
// We flow out from each of the entries, simultaneously.
// When we reach a new block, we add it as belonging to the one we got to
// it from. If we reach a new block that is already marked as belonging to
// someone, it is reachable by two entries and is not valid for any of
// them. Remove it and all it can reach that have been visited.
// Being in the queue means we just added this item, and we need to add
// its children
BlockList Queue;
for (auto* Entry : Entries) {
Helper.Ownership[Entry] = Entry;
IndependentGroups[Entry].insert(Entry);
Queue.push_back(Entry);
}
while (Queue.size() > 0) {
Block* Curr = Queue.front();
Queue.pop_front();
// Curr must be in the ownership map if we are in the queue
Block* Owner = Helper.Ownership[Curr];
if (!Owner) {
// we have been invalidated meanwhile after being reached from two
// entries
continue;
}
// Add all children
for (auto& [New, _] : Curr->BranchesOut) {
auto Known = Helper.Ownership.find(New);
if (Known == Helper.Ownership.end()) {
// New node. Add it, and put it in the queue
Helper.Ownership[New] = Owner;
IndependentGroups[Owner].insert(New);
Queue.push_back(New);
continue;
}
Block* NewOwner = Known->second;
if (!NewOwner) {
continue; // We reached an invalidated node
}
if (NewOwner != Owner) {
// Invalidate this and all reachable that we have seen - we reached
// this from two locations
Helper.InvalidateWithChildren(New);
}
// otherwise, we have the same owner, so do nothing
}
}
// Having processed all the interesting blocks, we remain with just one
// potential issue: If a->b, and a was invalidated, but then b was later
// reached by someone else, we must invalidate b. To check for this, we go
// over all elements in the independent groups, if an element has a parent
// which does *not* have the same owner, we must remove it and all its
// children.
for (auto* Entry : Entries) {
BlockSet& CurrGroup = IndependentGroups[Entry];
BlockList ToInvalidate;
for (auto* Child : CurrGroup) {
for (auto* Parent : Child->BranchesIn) {
if (Ignore && contains(*Ignore, Parent)) {
continue;
}
if (Helper.Ownership[Parent] != Helper.Ownership[Child]) {
ToInvalidate.push_back(Child);
}
}
}
while (ToInvalidate.size() > 0) {
Block* Invalidatee = ToInvalidate.front();
ToInvalidate.pop_front();
Helper.InvalidateWithChildren(Invalidatee);
}
}
// Remove empty groups
for (auto* Entry : Entries) {
if (IndependentGroups[Entry].size() == 0) {
IndependentGroups.erase(Entry);
}
}
#ifdef RELOOPER_DEBUG
PrintDebug("Investigated independent groups:\n");
for (auto& iter : IndependentGroups) {
DebugDump(iter.second, " group: ");
}
#endif
}
Shape* MakeMultiple(BlockSet& Blocks,
BlockSet& Entries,
BlockBlockSetMap& IndependentGroups,
BlockSet& NextEntries,
bool IsCheckedMultiple) {
PrintDebug("creating multiple block with %d inner groups\n",
IndependentGroups.size());
MultipleShape* Multiple = Parent->AddMultipleShape();
BlockSet CurrEntries;
for (auto& [CurrEntry, CurrBlocks] : IndependentGroups) {
PrintDebug(" multiple group with entry %d:\n", CurrEntry->Id);
DebugDump(CurrBlocks, " ");
// Create inner block
CurrEntries.clear();
CurrEntries.insert(CurrEntry);
for (auto* CurrInner : CurrBlocks) {
// Remove the block from the remaining blocks
Blocks.erase(CurrInner);
// Find new next entries and fix branches to them
for (auto iter = CurrInner->BranchesOut.begin();
iter != CurrInner->BranchesOut.end();) {
Block* CurrTarget = iter->first;
auto Next = iter;
Next++;
if (!contains(CurrBlocks, CurrTarget)) {
NextEntries.insert(CurrTarget);
Solipsize(CurrTarget, Branch::Break, Multiple, CurrBlocks);
}
iter = Next; // increment carefully because Solipsize can remove us
}
}
Multiple->InnerMap[CurrEntry->Id] = Process(CurrBlocks, CurrEntries);
if (IsCheckedMultiple) {
CurrEntry->IsCheckedMultipleEntry = true;
}
}
DebugDump(Blocks, " remaining blocks after multiple:");
// Add entries not handled as next entries, they are deferred
for (auto* Entry : Entries) {
if (!contains(IndependentGroups, Entry)) {
NextEntries.insert(Entry);
}
}
return Multiple;
}
// Main function.
// Process a set of blocks with specified entries, returns a shape
// The Make* functions receive a NextEntries. If they fill it with data,
// those are the entries for the
// ->Next block on them, and the blocks are what remains in Blocks (which
// Make* modify). In this way we avoid recursing on Next (imagine a long
// chain of Simples, if we recursed we could blow the stack).
Shape* Process(BlockSet& Blocks, BlockSet& InitialEntries) {
PrintDebug("Process() called\n", 0);
BlockSet* Entries = &InitialEntries;
BlockSet TempEntries[2];
int CurrTempIndex = 0;
BlockSet* NextEntries;
Shape* Ret = nullptr;
Shape* Prev = nullptr;
#define Make(call) \
Shape* Temp = call; \
if (Prev) \
Prev->Next = Temp; \
if (!Ret) \
Ret = Temp; \
if (!NextEntries->size()) { \
PrintDebug("Process() returning\n", 0); \
return Ret; \
} \
Prev = Temp; \
Entries = NextEntries; \
continue;
while (1) {
PrintDebug("Process() running\n", 0);
DebugDump(Blocks, " blocks : ");
DebugDump(*Entries, " entries: ");
CurrTempIndex = 1 - CurrTempIndex;
NextEntries = &TempEntries[CurrTempIndex];
NextEntries->clear();
if (Entries->size() == 0) {
return Ret;
}
if (Entries->size() == 1) {
Block* Curr = *(Entries->begin());
if (Curr->BranchesIn.size() == 0) {
// One entry, no looping ==> Simple
Make(MakeSimple(Blocks, Curr, *NextEntries));
}
// One entry, looping ==> Loop
Make(MakeLoop(Blocks, *Entries, *NextEntries));
}
// More than one entry, try to eliminate through a Multiple groups of
// independent blocks from an entry/ies. It is important to remove
// through multiples as opposed to looping since the former is more
// performant.
BlockBlockSetMap IndependentGroups;
FindIndependentGroups(*Entries, IndependentGroups);
PrintDebug("Independent groups: %d\n", IndependentGroups.size());
if (IndependentGroups.size() > 0) {
// We can handle a group in a multiple if its entry cannot be reached
// by another group. Note that it might be reachable by itself - a
// loop. But that is fine, we will create a loop inside the multiple
// block, which is both the performant order to do it, and preserves
// the property that a loop will always reach an entry.
for (auto iter = IndependentGroups.begin();
iter != IndependentGroups.end();) {
Block* Entry = iter->first;
BlockSet& Group = iter->second;
auto curr = iter++; // iterate carefully, we may delete
for (auto iterBranch = Entry->BranchesIn.begin();
iterBranch != Entry->BranchesIn.end();
iterBranch++) {
Block* Origin = *iterBranch;
if (!contains(Group, Origin)) {
// Reached from outside the group, so we cannot handle this
PrintDebug("Cannot handle group with entry %d because of "
"incoming branch from %d\n",
Entry->Id,
Origin->Id);
IndependentGroups.erase(curr);
break;
}
}
}
// As an optimization, if we have 2 independent groups, and one is a
// small dead end, we can handle only that dead end. The other then
// becomes a Next - without nesting in the code and recursion in the
// analysis.
// TODO: if the larger is the only dead end, handle that too
// TODO: handle >2 groups
// TODO: handle not just dead ends, but also that do not branch to the
// NextEntries. However, must be careful
// there since we create a Next, and that Next can prevent
// eliminating a break (since we no longer naturally reach the
// same place), which may necessitate a one-time loop, which
// makes the unnesting pointless.
if (IndependentGroups.size() == 2) {
// Find the smaller one
auto iter = IndependentGroups.begin();
Block* SmallEntry = iter->first;
int SmallSize = iter->second.size();
iter++;
Block* LargeEntry = iter->first;
int LargeSize = iter->second.size();
// ignore the case where they are identical - keep things
// symmetrical there
if (SmallSize != LargeSize) {
if (SmallSize > LargeSize) {
Block* Temp = SmallEntry;
SmallEntry = LargeEntry;
// Note: we did not flip the Sizes too, they are now invalid.
// TODO: use the smaller size as a limit?
LargeEntry = Temp;
}
// Check if dead end
bool DeadEnd = true;
BlockSet& SmallGroup = IndependentGroups[SmallEntry];
for (auto* Curr : SmallGroup) {
for (auto& [Target, _] : Curr->BranchesOut) {
if (!contains(SmallGroup, Target)) {
DeadEnd = false;
break;
}
}
if (!DeadEnd) {
break;
}
}
if (DeadEnd) {
PrintDebug("Removing nesting by not handling large group "
"because small group is dead end\n",
0);
IndependentGroups.erase(LargeEntry);
}
}
}
PrintDebug("Handleable independent groups: %d\n",
IndependentGroups.size());
if (IndependentGroups.size() > 0) {
// Some groups removable ==> Multiple
// This is a checked multiple if it has an entry that is an entry to
// this Process call, that is, if we can reach it from outside this
// set of blocks, then we must check the label variable to do so.
// Otherwise, if it is just internal blocks, those can always be
// jumped to forward, without using the label variable
bool Checked = false;
for (auto* Entry : *Entries) {
if (InitialEntries.count(Entry)) {
Checked = true;
break;
}
}
Make(MakeMultiple(
Blocks, *Entries, IndependentGroups, *NextEntries, Checked));
}
}
// No independent groups, must be loopable ==> Loop
Make(MakeLoop(Blocks, *Entries, *NextEntries));
}
}
};
// Main
BlockSet AllBlocks;
for (auto* Curr : Live.Live) {
AllBlocks.insert(Curr);
#ifdef RELOOPER_DEBUG
PrintDebug("Adding block %d (%s)\n", Curr->Id, Curr->Code);
#endif
}
BlockSet Entries;
Entries.insert(Entry);
Root = Analyzer(this).Process(AllBlocks, Entries);
assert(Root);
}
wasm::Expression* Relooper::Render(RelooperBuilder& Builder) {
assert(Root);
auto* ret = Root->Render(Builder, false);
// we may use the same name for more than one block in HandleFollowupMultiples
wasm::UniqueNameMapper::uniquify(ret);
return ret;
}
#ifdef RELOOPER_DEBUG
// Debugging
void Debugging::Dump(Block* Curr, const char* prefix) {
if (prefix)
std::cout << prefix << ": ";
std::cout << Curr->Id << " [code " << *Curr->Code << "] [switch? "
<< !!Curr->SwitchCondition << "]\n";
for (auto iter2 = Curr->BranchesOut.begin(); iter2 != Curr->BranchesOut.end();
iter2++) {
Block* Other = iter2->first;
Branch* Br = iter2->second;
std::cout << " -> " << Other->Id << ' ';
if (Br->Condition) {
std::cout << "[if " << *Br->Condition << "] ";
} else if (Br->SwitchValues) {
std::cout << "[cases ";
for (auto x : *Br->SwitchValues) {
std::cout << x << ' ';
}
std::cout << "] ";
} else {
std::cout << "[default] ";
}
if (Br->Code)
std::cout << "[phi " << *Br->Code << "] ";
std::cout << '\n';
}
std::cout << '\n';
}
void Debugging::Dump(BlockSet& Blocks, const char* prefix) {
if (prefix)
std::cout << prefix << ": ";
for (auto* Curr : Blocks) {
Dump(Curr);
}
}
void Debugging::Dump(Shape* S, const char* prefix) {
if (prefix)
std::cout << prefix << ": ";
if (!S) {
printf(" (null)\n");
return;
}
printf(" %d ", S->Id);
if (SimpleShape* Simple = Shape::IsSimple(S)) {
printf("<< Simple with block %d\n", Simple->Inner->Id);
} else if (MultipleShape* Multiple = Shape::IsMultiple(S)) {
printf("<< Multiple\n");
for (auto& [Entry, _] : Multiple->InnerMap) {
printf(" with entry %d\n", Entry);
}
} else if (Shape::IsLoop(S)) {
printf("<< Loop\n");
} else {
abort();
}
}
static void PrintDebug(const char* Format, ...) {
printf("// ");
va_list Args;
va_start(Args, Format);
vprintf(Format, Args);
va_end(Args);
}
#endif
} // namespace CFG