diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/ast_utils.h | 17 | ||||
| -rw-r--r-- | src/binaryen-c.cpp | 44 | ||||
| -rw-r--r-- | src/binaryen-c.h | 39 | ||||
| -rw-r--r-- | src/cfg/Relooper.cpp | 881 | ||||
| -rw-r--r-- | src/cfg/Relooper.h | 365 | ||||
| -rw-r--r-- | src/wasm-builder.h | 27 |
6 files changed, 1368 insertions, 5 deletions
diff --git a/src/ast_utils.h b/src/ast_utils.h index 8aacb62da..ebb6861da 100644 --- a/src/ast_utils.h +++ b/src/ast_utils.h @@ -119,6 +119,23 @@ struct EffectAnalyzer : public PostWalker<EffectAnalyzer, Visitor<EffectAnalyzer void visitUnreachable(Unreachable *curr) { branches = true; } }; +// Meausure the size of an AST +struct Measurer : public PostWalker<Measurer, UnifiedExpressionVisitor<Measurer>> { + size_t size = 0; + + void visitExpression(Expression* curr) { + size++; + } + + static bool measure(Expression* tree) { + Measurer measurer; + measurer.walk(tree); + return measurer.size; + } +}; + +// Manipulate expressions + struct ExpressionManipulator { // Re-use a node's memory. This helps avoid allocation when optimizing. template<typename InputType, typename OutputType> diff --git a/src/binaryen-c.cpp b/src/binaryen-c.cpp index 35baa8c35..b2c695ec0 100644 --- a/src/binaryen-c.cpp +++ b/src/binaryen-c.cpp @@ -22,6 +22,7 @@ #include "wasm.h" #include "wasm-builder.h" #include "wasm-printing.h" +#include "cfg/Relooper.h" using namespace wasm; @@ -383,4 +384,47 @@ void BinaryenModulePrint(BinaryenModuleRef module) { WasmPrinter::printModule((Module*)module); } +// +// ========== CFG / Relooper ========== +// + +RelooperRef RelooperCreate() { + return RelooperRef(new CFG::Relooper()); +} + +RelooperBlockRef RelooperAddBlock(RelooperRef relooper, BinaryenExpressionRef code) { + auto* R = (CFG::Relooper*)relooper; + auto* ret = new CFG::Block((Expression*)code); + R->AddBlock(ret); + return RelooperRef(ret); +} + +void RelooperAddBranch(RelooperBlockRef from, RelooperBlockRef to, BinaryenExpressionRef condition, BinaryenExpressionRef code) { + auto* fromBlock = (CFG::Block*)from; + auto* toBlock = (CFG::Block*)to; + fromBlock->AddBranchTo(toBlock, (Expression*)condition, (Expression*)code); +} + +RelooperBlockRef RelooperAddBlockWithSwitch(RelooperRef relooper, BinaryenExpressionRef code, BinaryenExpressionRef condition) { + auto* R = (CFG::Relooper*)relooper; + auto* ret = new CFG::Block((Expression*)code, (Expression*)condition); + R->AddBlock(ret); + return RelooperRef(ret); +} + +void RelooperAddBranchForSwitch(RelooperBlockRef from, RelooperBlockRef to, BinaryenIndex index, BinaryenExpressionRef code) { + auto* fromBlock = (CFG::Block*)from; + auto* toBlock = (CFG::Block*)to; + fromBlock->AddBranchTo(toBlock, (wasm::Index)index, (Expression*)code); +} + +BinaryenExpressionRef RelooperRenderAndDispose(RelooperRef relooper, RelooperBlockRef entry, BinaryenIndex labelHelper, BinaryenModuleRef module) { + auto* R = (CFG::Relooper*)relooper; + R->Calculate((CFG::Block*)entry); + CFG::RelooperBuilder builder(*(Module*)module, labelHelper); + auto* ret = R->Render(builder); + delete R; + return BinaryenExpressionRef(ret); +} + } // extern "C" diff --git a/src/binaryen-c.h b/src/binaryen-c.h index 09eda1458..2dbf27076 100644 --- a/src/binaryen-c.h +++ b/src/binaryen-c.h @@ -18,7 +18,11 @@ // Binaryen C API // // The first part of the API lets you create modules and their parts. +// // The second part of the API lets you perform operations on modules. +// +// The third part of the API lets you provide a general control-flow +// graph (CFG) as input. //================ #ifndef binaryen_h @@ -262,6 +266,41 @@ void BinaryenSetStart(BinaryenModuleRef module, const char* name); // Print a module to stdout. void BinaryenModulePrint(BinaryenModuleRef module); +// +// ========== CFG / Relooper ========== +// +// General usage is (1) create a relooper, (2) create blocks, (3) add +// branches between them, (4) render the output. +// +// See Relooper.h for more details + +typedef void* RelooperRef; +typedef void* RelooperBlockRef; + +// Create a relooper instance +RelooperRef RelooperCreate(); + +// Create a basic block that ends with nothing, or with some simple branching +RelooperBlockRef RelooperAddBlock(RelooperRef relooper, BinaryenExpressionRef code); + +// Create a branch to another basic block +// The branch can have code on it, that is executed as the branch happens. this is useful for phis. otherwise, code can be NULL +void RelooperAddBranch(RelooperBlockRef from, RelooperBlockRef to, BinaryenExpressionRef condition, BinaryenExpressionRef code); + +// Create a basic block that ends a switch on a condition +RelooperBlockRef RelooperAddBlockWithSwitch(RelooperRef relooper, BinaryenExpressionRef code, BinaryenExpressionRef condition); + +// Create a switch-style branch to another basic block. The block's switch table will have an index for this branch +void RelooperAddBranchForSwitch(RelooperBlockRef from, RelooperBlockRef to, BinaryenIndex index, BinaryenExpressionRef code); + +// Generate structed wasm control flow from the CFG of blocks and branches that were created +// on this relooper instance. This returns the rendered output, and also disposes of the +// relooper and its blocks and branches, as they are no longer needed. +// @param labelHelper To render irreducible control flow, we may need a helper variable to +// guide us to the right target label. This value should be an index of +// an i32 local variable that is free for us to use. +BinaryenExpressionRef RelooperRenderAndDispose(RelooperRef relooper, RelooperBlockRef entry, BinaryenIndex labelHelper, BinaryenModuleRef module); + #ifdef __cplusplus } // extern "C" #endif diff --git a/src/cfg/Relooper.cpp b/src/cfg/Relooper.cpp new file mode 100644 index 000000000..f791a3c13 --- /dev/null +++ b/src/cfg/Relooper.cpp @@ -0,0 +1,881 @@ +/* + * 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 <string.h> +#include <stdlib.h> +#include <list> +#include <stack> +#include <string> + +#include "ast_utils.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 + +// Branch + +Branch::Branch(wasm::Expression* ConditionInit, wasm::Expression* CodeInit) : Ancestor(NULL), Condition(ConditionInit), Code(CodeInit) {} + +Branch::Branch(wasm::Index IndexInit, wasm::Expression* CodeInit) : Ancestor(NULL), Index(IndexInit), Code(CodeInit) {} + +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 (Ancestor) { + if (Type == Break) { + Ret->list.push_back(Builder.makeBreak(Ancestor->Id)); + } else if (Type == Continue) { + Ret->list.push_back(Builder.makeContinue(Ancestor->Id)); + } + } + return Ret; +} + +// Block + +Block::Block(wasm::Expression* CodeInit, wasm::Expression* SwitchConditionInit) : Parent(NULL), Id(-1), Code(CodeInit), SwitchCondition(SwitchConditionInit), IsCheckedMultipleEntry(false) {} + +Block::~Block() { + for (BlockBranchMap::iterator iter = ProcessedBranchesOut.begin(); iter != ProcessedBranchesOut.end(); iter++) { + delete iter->second; + } +} + +void Block::AddBranchTo(Block *Target, wasm::Expression* Condition, wasm::Expression* Code) { + assert(!contains(BranchesOut, Target)); // cannot add more than one branch to the same target + BranchesOut[Target] = new Branch(Condition, Code); +} + +void Block::AddBranchTo(Block *Target, wasm::Index Index, wasm::Expression* Code) { + assert(!contains(BranchesOut, Target)); // cannot add more than one branch to the same target + BranchesOut[Target] = new Branch(Index, 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()) return Ret; + + bool SetLabel = true; // in some cases it is clear we can avoid setting label, see later + bool ForceSetLabel = Shape::IsEmulated(Parent); + + // 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 (SetLabel && Fused->InnerMap.size() == ProcessedBranchesOut.size()) { + SetLabel = false; + } + } + + Block *DefaultTarget = nullptr; // The block we branch to without checking the condition, if none of the other conditions held. + + // Find the default target, the one without a condition + for (BlockBranchMap::iterator iter = ProcessedBranchesOut.begin(); iter != ProcessedBranchesOut.end(); iter++) { + if (!iter->second->Condition) { + assert(!DefaultTarget && "block has branches without a default (NULL for the condition)"); // Must be exactly one default + DefaultTarget = iter->first; + } + } + assert(DefaultTarget); // Since each block *must* branch somewhere, this must be set + + if (SwitchCondition) { + abort(); // TODO: switch + } + + // We'll emit a chain of if-elses + wasm::Expression* Root = nullptr; + wasm::If* CurrIf = nullptr; + + wasm::Expression* RemainingConditions = nullptr; + + for (BlockBranchMap::iterator 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; + assert(Details->Condition); // must have a condition if this is not the default target + } else { + Target = DefaultTarget; + Details = ProcessedBranchesOut[DefaultTarget]; + } + bool SetCurrLabel = (SetLabel && Target->IsCheckedMultipleEntry) || ForceSetLabel; + bool HasFusedContent = Fused && contains(Fused->InnerMap, Target->Id); + 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)); + } else if (Details->Type == Branch::Nested) { + // Nest the parent content here, and remove it from showing up afterwards as Next + assert(Parent->Next); + CurrContent = Builder.blockify(CurrContent, Parent->Next->Render(Builder, InLoop)); + Parent->Next = nullptr; + } + } + bool isDefault = iter == ProcessedBranchesOut.end(); + // 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); + } else { + Now = CurrContent; + } + if (!CurrIf) { + assert(!Root); + Root = Now; + } else { + CurrIf->ifFalse = Now; + } + } else { + auto* Now = Builder.makeIf(Details->Condition, CurrContent); + if (!CurrIf) { + assert(!Root); + Root = CurrIf = Now; + } else { + CurrIf->ifFalse = Now; + CurrIf = Now; + } + } + } else { + auto* Now = Builder.makeUnary(wasm::EqZ, Details->Condition); + if (RemainingConditions) { + RemainingConditions = Builder.makeBinary(wasm::And, RemainingConditions, Now); + } else { + RemainingConditions = Now; + } + } + if (isDefault) break; + } + + if (Root) { + if (Fused) { + // We are fusing a multiple into this simple + auto* Block = Builder.makeBlock(Root); + Block->name = Builder.getBreakName(Fused->Id); + Root = Block; + } + Ret->list.push_back(Root); + } + + return Ret; +} + +// SimpleShape + +wasm::Expression* SimpleShape::Render(RelooperBuilder& Builder, bool InLoop) { + auto* Ret = Inner->Render(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, *CurrIf = nullptr; + for (IdShapeMap::iterator iter = InnerMap.begin(); iter != InnerMap.end(); iter++) { + auto* Now = Builder.makeIf( + Builder.makeCheckLabel(iter->first), + iter->second->Render(Builder, InLoop) + ); + if (!CurrIf) { + FirstIf = CurrIf = Now; + } else { + CurrIf->ifFalse = Now; + CurrIf = Now; + } + } + auto* Ret = Builder.makeBlock(FirstIf); + Ret->name = Builder.getBreakName(Id); + 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.getBreakName(Id), Builder.getContinueName(Id), Inner->Render(Builder, true)); + if (Next) { + Ret = Builder.makeSequence(Ret, Next->Render(Builder, InLoop)); + } + return Ret; +} + +// EmulatedShape + +wasm::Expression* EmulatedShape::Render(RelooperBuilder& Builder, bool InLoop) { + abort(); // TODO +} + +// Relooper + +Relooper::Relooper() : Root(nullptr), Emulate(false), MinSize(false), BlockIdCounter(1), ShapeIdCounter(0) { // block ID 0 is reserved for clearings +} + +Relooper::~Relooper() { + for (unsigned i = 0; i < Blocks.size(); i++) delete Blocks[i]; + for (unsigned i = 0; i < Shapes.size(); i++) delete Shapes[i]; +} + +void Relooper::AddBlock(Block *New, int Id) { + New->Id = Id == -1 ? BlockIdCounter++ : Id; + Blocks.push_back(New); +} + +struct RelooperRecursor { + Relooper *Parent; + RelooperRecursor(Relooper *ParentInit) : Parent(ParentInit) {} +}; + +typedef std::list<Block*> BlockList; + +void Relooper::Calculate(Block *Entry) { + // Scan and optimize the input + struct PreOptimizer : public RelooperRecursor { + PreOptimizer(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 (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { + ToInvestigate.push_back(iter->first); + } + } + } + }; + PreOptimizer Pre(this); + Pre.FindLive(Entry); + + // Add incoming branches from live blocks, ignoring dead code + for (unsigned i = 0; i < Blocks.size(); i++) { + Block *Curr = Blocks[i]; + if (!contains(Pre.Live, Curr)) continue; + for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { + iter->first->BranchesIn.insert(Curr); + } + } + + // Recursively process the graph + + struct Analyzer : public RelooperRecursor { + Analyzer(Relooper *Parent) : RelooperRecursor(Parent) {} + + // Add a shape to the list of shapes in this Relooper calculation + void Notice(Shape *New) { + New->Id = Parent->ShapeIdCounter++; + Parent->Shapes.push_back(New); + } + + // 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 (BlockBranchMap::iterator iter = Source->BranchesOut.begin(); iter != Source->BranchesOut.end(); iter++) { + if (!LimitTo || contains(*LimitTo, iter->first)) { + Entries.insert(iter->first); + } + } + } + + // 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 (BlockSet::iterator 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 = new SimpleShape; + Notice(Simple); + Simple->Inner = Inner; + Inner->Parent = Simple; + if (Blocks.size() > 1) { + Blocks.erase(Inner); + GetBlocksOut(Inner, NextEntries, &Blocks); + BlockSet JustInner; + JustInner.insert(Inner); + for (BlockSet::iterator iter = NextEntries.begin(); iter != NextEntries.end(); iter++) { + Solipsize(*iter, Branch::Direct, Simple, JustInner); + } + } + return Simple; + } + + Shape *MakeEmulated(BlockSet &Blocks, Block *Entry, BlockSet &NextEntries) { + PrintDebug("creating emulated block with entry #%d and everything it can reach, %d blocks\n", Entry->Id, Blocks.size()); + EmulatedShape *Emulated = new EmulatedShape; + Notice(Emulated); + Emulated->Entry = Entry; + for (BlockSet::iterator iter = Blocks.begin(); iter != Blocks.end(); iter++) { + Block *Curr = *iter; + Emulated->Blocks.insert(Curr); + Curr->Parent = Emulated; + Solipsize(Curr, Branch::Continue, Emulated, Blocks); + } + Blocks.clear(); + return Emulated; + } + + 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 (BlockSet::iterator iter = Curr->BranchesIn.begin(); iter != Curr->BranchesIn.end(); iter++) { + Queue.insert(*iter); + } +#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 (BlockBranchMap::iterator 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 (BlockSet::iterator iter = InnerBlocks.begin(); iter != InnerBlocks.end(); iter++) { + Block *Curr = *iter; + for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { + Block *Possible = iter->first; + 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 (BlockBlockSetMap::iterator 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 (BlockSet::iterator iter = Hoisted.begin(); iter != Hoisted.end() && !abort; iter++) { + Block *Curr = *iter; + for (BlockBranchMap::iterator 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 (BlockSet::iterator 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 = new LoopShape(); + Notice(Loop); + + // 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 (BlockSet::iterator iter = Entries.begin(); iter != Entries.end(); iter++) { + Solipsize(*iter, Branch::Continue, Loop, InnerBlocks); + } + // B. Branches to outside the loop (a next entry) become breaks on this shape + for (BlockSet::iterator iter = NextEntries.begin(); iter != NextEntries.end(); iter++) { + Solipsize(*iter, Branch::Break, Loop, InnerBlocks); + } + // Finish up + Shape *Inner = Process(InnerBlocks, Entries, nullptr); + Loop->Inner = Inner; + 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) { + typedef std::map<Block*, Block*> BlockBlockMap; + + struct HelperClass { + BlockBlockSetMap& IndependentGroups; + BlockBlockMap Ownership; // For each block, which entry it belongs to. We have reached it from there. + + HelperClass(BlockBlockSetMap& IndependentGroupsInit) : IndependentGroups(IndependentGroupsInit) {} + void InvalidateWithChildren(Block *New) { // TODO: rename New + BlockList ToInvalidate; // Being in the list means you need to be invalidated + ToInvalidate.push_back(New); + while (ToInvalidate.size() > 0) { + Block *Invalidatee = ToInvalidate.front(); + ToInvalidate.pop_front(); + Block *Owner = Ownership[Invalidatee]; + if (contains(IndependentGroups, Owner)) { // Owner may have been invalidated, do not add to IndependentGroups! + IndependentGroups[Owner].erase(Invalidatee); + } + if (Ownership[Invalidatee]) { // may have been seen before and invalidated already + Ownership[Invalidatee] = nullptr; + for (BlockBranchMap::iterator iter = Invalidatee->BranchesOut.begin(); iter != Invalidatee->BranchesOut.end(); iter++) { + Block *Target = iter->first; + BlockBlockMap::iterator 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. + + BlockList Queue; // Being in the queue means we just added this item, and we need to add its children + for (BlockSet::iterator iter = Entries.begin(); iter != Entries.end(); iter++) { + Block *Entry = *iter; + Helper.Ownership[Entry] = Entry; + IndependentGroups[Entry].insert(Entry); + Queue.push_back(Entry); + } + while (Queue.size() > 0) { + Block *Curr = Queue.front(); + Queue.pop_front(); + Block *Owner = Helper.Ownership[Curr]; // Curr must be in the ownership map if we are in the queue + if (!Owner) continue; // we have been invalidated meanwhile after being reached from two entries + // Add all children + for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { + Block *New = iter->first; + BlockBlockMap::iterator 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 (BlockSet::iterator iter = Entries.begin(); iter != Entries.end(); iter++) { + BlockSet &CurrGroup = IndependentGroups[*iter]; + BlockList ToInvalidate; + for (BlockSet::iterator iter = CurrGroup.begin(); iter != CurrGroup.end(); iter++) { + Block *Child = *iter; + for (BlockSet::iterator iter = Child->BranchesIn.begin(); iter != Child->BranchesIn.end(); iter++) { + Block *Parent = *iter; + 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 (BlockSet::iterator iter = Entries.begin(); iter != Entries.end(); iter++) { + if (IndependentGroups[*iter].size() == 0) { + IndependentGroups.erase(*iter); + } + } + +#ifdef RELOOPER_DEBUG + PrintDebug("Investigated independent groups:\n"); + for (BlockBlockSetMap::iterator iter = IndependentGroups.begin(); iter != IndependentGroups.end(); iter++) { + DebugDump(iter->second, " group: "); + } +#endif + } + + Shape *MakeMultiple(BlockSet &Blocks, BlockSet& Entries, BlockBlockSetMap& IndependentGroups, Shape *Prev, BlockSet &NextEntries) { + PrintDebug("creating multiple block with %d inner groups\n", IndependentGroups.size()); + bool Fused = !!(Shape::IsSimple(Prev)); + MultipleShape *Multiple = new MultipleShape(); + Notice(Multiple); + BlockSet CurrEntries; + for (BlockBlockSetMap::iterator iter = IndependentGroups.begin(); iter != IndependentGroups.end(); iter++) { + Block *CurrEntry = iter->first; + BlockSet &CurrBlocks = iter->second; + PrintDebug(" multiple group with entry %d:\n", CurrEntry->Id); + DebugDump(CurrBlocks, " "); + // Create inner block + CurrEntries.clear(); + CurrEntries.insert(CurrEntry); + for (BlockSet::iterator iter = CurrBlocks.begin(); iter != CurrBlocks.end(); iter++) { + Block *CurrInner = *iter; + // Remove the block from the remaining blocks + Blocks.erase(CurrInner); + // Find new next entries and fix branches to them + for (BlockBranchMap::iterator iter = CurrInner->BranchesOut.begin(); iter != CurrInner->BranchesOut.end();) { + Block *CurrTarget = iter->first; + BlockBranchMap::iterator 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, nullptr); + // If we are not fused, then our entries will actually be checked + if (!Fused) { + CurrEntry->IsCheckedMultipleEntry = true; + } + } + DebugDump(Blocks, " remaining blocks after multiple:"); + // Add entries not handled as next entries, they are deferred + for (BlockSet::iterator iter = Entries.begin(); iter != Entries.end(); iter++) { + Block *Entry = *iter; + 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, Shape *Prev) { + PrintDebug("Process() called\n", 0); + BlockSet *Entries = &InitialEntries; + BlockSet TempEntries[2]; + int CurrTempIndex = 0; + BlockSet *NextEntries; + Shape *Ret = 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 (Parent->Emulate) { + Make(MakeEmulated(Blocks, Curr, *NextEntries)); + } + 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 the performant order to do it). + for (BlockBlockSetMap::iterator iter = IndependentGroups.begin(); iter != IndependentGroups.end();) { + Block *Entry = iter->first; + BlockSet &Group = iter->second; + BlockBlockSetMap::iterator curr = iter++; // iterate carefully, we may delete + for (BlockSet::iterator 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 + BlockBlockSetMap::iterator iter = IndependentGroups.begin(); + Block *SmallEntry = iter->first; + int SmallSize = iter->second.size(); + iter++; + Block *LargeEntry = iter->first; + int LargeSize = iter->second.size(); + if (SmallSize != LargeSize) { // ignore the case where they are identical - keep things symmetrical there + if (SmallSize > LargeSize) { + Block *Temp = SmallEntry; + SmallEntry = LargeEntry; + LargeEntry = Temp; // Note: we did not flip the Sizes too, they are now invalid. TODO: use the smaller size as a limit? + } + // Check if dead end + bool DeadEnd = true; + BlockSet &SmallGroup = IndependentGroups[SmallEntry]; + for (BlockSet::iterator iter = SmallGroup.begin(); iter != SmallGroup.end(); iter++) { + Block *Curr = *iter; + for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { + Block *Target = iter->first; + 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 + Make(MakeMultiple(Blocks, *Entries, IndependentGroups, Prev, *NextEntries)); + } + } + // No independent groups, must be loopable ==> Loop + Make(MakeLoop(Blocks, *Entries, *NextEntries)); + } + } + }; + + // Main + + BlockSet AllBlocks; + for (BlockSet::iterator iter = Pre.Live.begin(); iter != Pre.Live.end(); iter++) { + Block *Curr = *iter; + 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, nullptr); + assert(Root); +} + +wasm::Expression* Relooper::Render(RelooperBuilder& Builder) { + assert(Root); + return Root->Render(Builder, false); +} + +#ifdef RELOOPER_DEBUG +// Debugging + +void Debugging::Dump(BlockSet &Blocks, const char *prefix) { + if (prefix) printf("%s ", prefix); + for (BlockSet::iterator iter = Blocks.begin(); iter != Blocks.end(); iter++) { + Block *Curr = *iter; + printf("%d:\n", Curr->Id); + for (BlockBranchMap::iterator iter2 = Curr->BranchesOut.begin(); iter2 != Curr->BranchesOut.end(); iter2++) { + Block *Other = iter2->first; + printf(" -> %d\n", Other->Id); + assert(contains(Other->BranchesIn, Curr)); + } + } +} + +void Debugging::Dump(Shape *S, const char *prefix) { + if (prefix) printf("%s ", 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 (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) { + printf(" with entry %d\n", iter->first); + } + } 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 diff --git a/src/cfg/Relooper.h b/src/cfg/Relooper.h new file mode 100644 index 000000000..efe6a3c8f --- /dev/null +++ b/src/cfg/Relooper.h @@ -0,0 +1,365 @@ +/* + * 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. + */ + +/* +This is an optimized C++ implemention of the Relooper algorithm originally +developed as part of Emscripten. This implementation includes optimizations +added since the original academic paper [1] was published about it. + +[1] Alon Zakai. 2011. Emscripten: an LLVM-to-JavaScript compiler. In Proceedings of the ACM international conference companion on Object oriented programming systems languages and applications companion (SPLASH '11). ACM, New York, NY, USA, 301-312. DOI=10.1145/2048147.2048224 http://doi.acm.org/10.1145/2048147.2048224 +*/ + +#include <assert.h> +#include <stdio.h> +#include <stdarg.h> +#include <stdlib.h> + +#include <map> +#include <deque> +#include <set> +#include <list> + +#include "wasm.h" +#include "wasm-builder.h" + +namespace CFG { + +class RelooperBuilder : public wasm::Builder { + wasm::Index labelHelper; + +public: + RelooperBuilder(wasm::Module& wasm, wasm::Index labelHelper) : wasm::Builder(wasm), labelHelper(labelHelper) {} + + wasm::GetLocal* makeGetLabel() { + return makeGetLocal(labelHelper, wasm::i32); + } + wasm::SetLocal* makeSetLabel(wasm::Index value) { + return makeSetLocal(labelHelper, makeConst(wasm::Literal(int32_t(value)))); + } + wasm::Binary* makeCheckLabel(wasm::Index value) { + return makeBinary(wasm::Eq, makeGetLabel(), makeConst(wasm::Literal(int32_t(value)))); + } + wasm::Break* makeBreak(int id) { + return wasm::Builder::makeBreak(getBreakName(id)); + } + wasm::Break* makeContinue(int id) { + return wasm::Builder::makeBreak(getContinueName(id)); + } + + wasm::Name getBreakName(int id) { + return wasm::Name(std::string("shape$") + std::to_string(id) + "$break"); + } + wasm::Name getContinueName(int id) { + return wasm::Name(std::string("shape$") + std::to_string(id) + "$continue"); + } +}; + +struct Block; +struct Shape; + +// Info about a branching from one block to another +struct Branch { + enum FlowType { + Direct = 0, // We will directly reach the right location through other means, no need for continue or break + Break = 1, + Continue = 2, + Nested = 3 // This code is directly reached, but we must be careful to ensure it is nested in an if - it is not reached + // unconditionally, other code paths exist alongside it that we need to make sure do not intertwine + }; + Shape *Ancestor; // If not NULL, this shape is the relevant one for purposes of getting to the target block. We break or continue on it + Branch::FlowType Type; // If Ancestor is not NULL, this says whether to break or continue + + // A branch either has a condition expression if the block ends in ifs, or if the block ends in a switch, then an index, which + // becomes the index in the table of the switch. + union { + wasm::Expression* Condition; // The condition for which we branch. For example, "my_var == 1". Conditions are checked one by one. One of the conditions should have NULL as the condition, in which case it is the default + wasm::Index Index; // The index in the table of the switch that we correspond do + }; + + wasm::Expression* Code; // If provided, code that is run right before the branch is taken. This is useful for phis + + Branch(wasm::Expression* ConditionInit, wasm::Expression* CodeInit = nullptr); + Branch(wasm::Index IndexInit, wasm::Expression* CodeInit = nullptr); + + // Emits code for branch + wasm::Expression* Render(RelooperBuilder& Builder, Block *Target, bool SetLabel); +}; + +// like std::set, except that begin() -> end() iterates in the +// order that elements were added to the set (not in the order +// of operator<(T, T)) +template<typename T> +struct InsertOrderedSet +{ + std::map<T, typename std::list<T>::iterator> Map; + std::list<T> List; + + typedef typename std::list<T>::iterator iterator; + iterator begin() { return List.begin(); } + iterator end() { return List.end(); } + + void erase(const T& val) { + auto it = Map.find(val); + if (it != Map.end()) { + List.erase(it->second); + Map.erase(it); + } + } + + void erase(iterator position) { + Map.erase(*position); + List.erase(position); + } + + // cheating a bit, not returning the iterator + void insert(const T& val) { + auto it = Map.find(val); + if (it == Map.end()) { + List.push_back(val); + Map.insert(std::make_pair(val, --List.end())); + } + } + + size_t size() const { return Map.size(); } + + void clear() { + Map.clear(); + List.clear(); + } + + size_t count(const T& val) const { return Map.count(val); } + + InsertOrderedSet() {} + InsertOrderedSet(const InsertOrderedSet& other) { + for (auto i : other.List) { + insert(i); // inserting manually creates proper iterators + } + } + InsertOrderedSet& operator=(const InsertOrderedSet& other) { + abort(); // TODO, watch out for iterators + } +}; + +// like std::map, except that begin() -> end() iterates in the +// order that elements were added to the map (not in the order +// of operator<(Key, Key)) +template<typename Key, typename T> +struct InsertOrderedMap +{ + std::map<Key, typename std::list<std::pair<Key,T>>::iterator> Map; + std::list<std::pair<Key,T>> List; + + T& operator[](const Key& k) { + auto it = Map.find(k); + if (it == Map.end()) { + List.push_back(std::make_pair(k, T())); + auto e = --List.end(); + Map.insert(std::make_pair(k, e)); + return e->second; + } + return it->second->second; + } + + typedef typename std::list<std::pair<Key,T>>::iterator iterator; + iterator begin() { return List.begin(); } + iterator end() { return List.end(); } + + void erase(const Key& k) { + auto it = Map.find(k); + if (it != Map.end()) { + List.erase(it->second); + Map.erase(it); + } + } + + void erase(iterator position) { + erase(position->first); + } + + size_t size() const { return Map.size(); } + size_t count(const Key& k) const { return Map.count(k); } + + InsertOrderedMap() {} + InsertOrderedMap(InsertOrderedMap& other) { + abort(); // TODO, watch out for iterators + } + InsertOrderedMap& operator=(const InsertOrderedMap& other) { + abort(); // TODO, watch out for iterators + } +}; + + +typedef InsertOrderedSet<Block*> BlockSet; +typedef InsertOrderedMap<Block*, Branch*> BlockBranchMap; + +// Represents a basic block of code - some instructions that end with a +// control flow modifier (a branch, return or throw). +struct Block { + // Branches become processed after we finish the shape relevant to them. For example, + // when we recreate a loop, branches to the loop start become continues and are now + // processed. When we calculate what shape to generate from a set of blocks, we ignore + // processed branches. + // Blocks own the Branch objects they use, and destroy them when done. + BlockBranchMap BranchesOut; + BlockSet BranchesIn; + BlockBranchMap ProcessedBranchesOut; + BlockSet ProcessedBranchesIn; + Shape *Parent; // The shape we are directly inside + int Id; // A unique identifier, defined when added to relooper. Note that this uniquely identifies a *logical* block - if we split it, the two instances have the same content *and* the same Id + wasm::Expression* Code; // The code in this block. This can be arbitrary wasm code, including internal control flow, it should just not branch to the outside + wasm::Expression* SwitchCondition; // If nullptr, then this block ends in ifs (or nothing). otherwise, this block ends in a switch, done on this condition + bool IsCheckedMultipleEntry; // If true, we are a multiple entry, so reaching us requires setting the label variable + + Block(wasm::Expression* CodeInit, wasm::Expression* SwitchConditionInit = nullptr); + ~Block(); + + void AddBranchTo(Block *Target, wasm::Expression* Condition, wasm::Expression* Code = nullptr); + void AddBranchTo(Block *Target, wasm::Index Index, wasm::Expression* Code = nullptr); + + // Emit code for the block, including its contents and branchings out + wasm::Expression* Render(RelooperBuilder& Builder, bool InLoop); +}; + +// Represents a structured control flow shape, one of +// +// Simple: No control flow at all, just instructions. If several +// blocks, then +// +// Multiple: A shape with more than one entry. If the next block to +// be entered is among them, we run it and continue to +// the next shape, otherwise we continue immediately to the +// next shape. +// +// Loop: An infinite loop. +// +// Emulated: Control flow is managed by a switch in a loop. This +// is necessary in some cases, for example when control +// flow is not known until runtime (indirect branches, +// setjmp returns, etc.) +// + +struct SimpleShape; +struct MultipleShape; +struct LoopShape; +struct EmulatedShape; + +struct Shape { + int Id; // A unique identifier. Used to identify loops, labels are Lx where x is the Id. Defined when added to relooper + Shape *Next; // The shape that will appear in the code right after this one + Shape *Natural; // The shape that control flow gets to naturally (if there is Next, then this is Next) + + enum ShapeType { + Simple, + Multiple, + Loop, + Emulated + }; + ShapeType Type; + + Shape(ShapeType TypeInit) : Id(-1), Next(NULL), Type(TypeInit) {} + virtual ~Shape() {} + + virtual wasm::Expression* Render(RelooperBuilder& Builder, bool InLoop) = 0; + + static SimpleShape *IsSimple(Shape *It) { return It && It->Type == Simple ? (SimpleShape*)It : NULL; } + static MultipleShape *IsMultiple(Shape *It) { return It && It->Type == Multiple ? (MultipleShape*)It : NULL; } + static LoopShape *IsLoop(Shape *It) { return It && It->Type == Loop ? (LoopShape*)It : NULL; } + static EmulatedShape *IsEmulated(Shape *It) { return It && It->Type == Emulated ? (EmulatedShape*)It : NULL; } +}; + +struct SimpleShape : public Shape { + Block *Inner; + + SimpleShape() : Shape(Simple), Inner(NULL) {} + wasm::Expression* Render(RelooperBuilder& Builder, bool InLoop) override; +}; + +// Blocks with the same id were split and are identical, so we just care about ids in Multiple entries +typedef std::map<int, Shape*> IdShapeMap; + +struct MultipleShape : public Shape { + IdShapeMap InnerMap; // entry block ID -> shape + + MultipleShape() : Shape(Multiple) {} + + wasm::Expression* Render(RelooperBuilder& Builder, bool InLoop) override; +}; + +struct LoopShape : public Shape { + Shape *Inner; + + LoopShape() : Shape(Loop), Inner(NULL) {} + wasm::Expression* Render(RelooperBuilder& Builder, bool InLoop) override; +}; + +// TODO EmulatedShape is only partially functional. Currently it can be used for the +// entire set of blocks being relooped, but not subsets. +struct EmulatedShape : public Shape { + Block *Entry; + BlockSet Blocks; + + EmulatedShape() : Shape(Emulated) { } + wasm::Expression* Render(RelooperBuilder& Builder, bool InLoop) override; +}; + +// Implements the relooper algorithm for a function's blocks. +// +// Usage: +// 1. Instantiate this struct. +// 2. Call AddBlock with the blocks you have. Each should already +// have its branchings in specified (the branchings out will +// be calculated by the relooper). +// 3. Call Render(). +// +// Implementation details: The Relooper instance has +// ownership of the blocks and shapes, and frees them when done. +struct Relooper { + std::deque<Block*> Blocks; + std::deque<Shape*> Shapes; + Shape *Root; + bool Emulate; + bool MinSize; + int BlockIdCounter; + int ShapeIdCounter; + + Relooper(); + ~Relooper(); + + void AddBlock(Block *New, int Id=-1); + + // Calculates the shapes + void Calculate(Block *Entry); + + // Renders the result. + wasm::Expression* Render(RelooperBuilder& Builder); + + // Sets whether we must emulate everything with switch-loop code + void SetEmulate(int E) { Emulate = E; } + + // Sets us to try to minimize size + void SetMinSize(bool MinSize_) { MinSize = MinSize_; } +}; + +typedef InsertOrderedMap<Block*, BlockSet> BlockBlockSetMap; + +#ifdef RELOOPER_DEBUG +struct Debugging { + static void Dump(BlockSet &Blocks, const char *prefix=NULL); + static void Dump(Shape *S, const char *prefix=NULL); +}; +#endif + +} // namespace CFG diff --git a/src/wasm-builder.h b/src/wasm-builder.h index 8f0d4838a..c20c25f06 100644 --- a/src/wasm-builder.h +++ b/src/wasm-builder.h @@ -64,7 +64,9 @@ public: return func; } - // Nop TODO: add all the rest + Nop* makeNop() { + return allocator.alloc<Nop>(); + } Block* makeBlock(Expression* first = nullptr) { auto* ret = allocator.alloc<Block>(); if (first) { @@ -224,10 +226,25 @@ public: func->localIndices.clear(); } - // ensure a node is a block, if it isn't already - Block* blockify(Expression* any) { - if (any->is<Block>()) return any->cast<Block>(); - return makeBlock(any); + // ensure a node is a block, if it isn't already, and optionally append to the block + Block* blockify(Expression* any, Expression* append = nullptr) { + Block* block = nullptr; + if (any) block = any->dynCast<Block>(); + if (!block) block = makeBlock(any); + if (append) { + block->list.push_back(append); + block->finalize(); + } + return block; + } + + // a helper for the common pattern of a sequence of two expressions. Similar to + // blockify, but does *not* reuse a block if the first is one. + Block* makeSequence(Expression* left, Expression* right) { + auto* block = makeBlock(left); + block->list.push_back(right); + block->finalize(); + return block; } }; |