diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/cfg/Relooper.cpp | 125 | ||||
| -rw-r--r-- | src/cfg/Relooper.h | 50 |
2 files changed, 121 insertions, 54 deletions
diff --git a/src/cfg/Relooper.cpp b/src/cfg/Relooper.cpp index 6488b3d06..cde61df0b 100644 --- a/src/cfg/Relooper.cpp +++ b/src/cfg/Relooper.cpp @@ -18,6 +18,7 @@ #include <string.h> #include <stdlib.h> + #include <list> #include <stack> #include <string> @@ -38,6 +39,59 @@ static void PrintDebug(const char *Format, ...); #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& iter : Multiple->InnerMap) { + int Id = iter.first; + Shape* Body = iter.second; + Curr->name = Builder.getBlockBreakName(Id); + 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); + auto* Outer = Builder.makeBlock(Curr); + Outer->finalize(); // TODO: not really necessary + Curr = Outer; + } + } + } + } + return Curr; +} + // Branch Branch::Branch(wasm::Expression* ConditionInit, wasm::Expression* CodeInit) : Ancestor(nullptr), Condition(ConditionInit), Code(CodeInit) {} @@ -53,12 +107,11 @@ wasm::Expression* Branch::Render(RelooperBuilder& Builder, Block *Target, bool S 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.makeShapeBreak(Ancestor->Id)); - } else if (Type == Continue) { - Ret->list.push_back(Builder.makeShapeContinue(Ancestor->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; @@ -128,7 +181,6 @@ wasm::Expression* Block::Render(RelooperBuilder& Builder, bool InLoop) { 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 @@ -171,22 +223,21 @@ wasm::Expression* Block::Render(RelooperBuilder& Builder, bool InLoop) { } 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)); - } 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) { + if (IsDefault) { wasm::Expression* Now; if (RemainingConditions) { Now = Builder.makeIf(RemainingConditions, CurrContent); @@ -217,7 +268,7 @@ wasm::Expression* Block::Render(RelooperBuilder& Builder, bool InLoop) { RemainingConditions = Now; } } - if (isDefault) break; + if (IsDefault) break; } } else { // Emit a switch @@ -240,16 +291,15 @@ wasm::Expression* Block::Render(RelooperBuilder& Builder, bool InLoop) { // 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)); - } 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; } } // generate a block to branch to, if we have content @@ -285,15 +335,8 @@ wasm::Expression* Block::Render(RelooperBuilder& Builder, bool InLoop) { } 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); } - Ret->finalize(); return Ret; @@ -303,6 +346,7 @@ wasm::Expression* Block::Render(RelooperBuilder& Builder, bool InLoop) { 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)); } @@ -328,8 +372,8 @@ wasm::Expression* MultipleShape::Render(RelooperBuilder& Builder, bool InLoop) { CurrIf = Now; } } - auto* Ret = Builder.makeBlock(FirstIf); - Ret->name = Builder.getBreakName(Id); + wasm::Expression* Ret = Builder.makeBlock(FirstIf); + Ret = HandleFollowupMultiples(Ret, this, Builder, InLoop); if (Next) { Ret = Builder.makeSequence(Ret, Next->Render(Builder, InLoop)); } @@ -339,7 +383,8 @@ wasm::Expression* MultipleShape::Render(RelooperBuilder& Builder, bool InLoop) { // LoopShape wasm::Expression* LoopShape::Render(RelooperBuilder& Builder, bool InLoop) { - wasm::Expression* Ret = Builder.makeLoop(Builder.getBreakName(Id), Builder.getContinueName(Id), Inner->Render(Builder, true)); + wasm::Expression* Ret = Builder.makeLoop(wasm::Name(), Builder.getShapeContinueName(Id), Inner->Render(Builder, true)); + Ret = HandleFollowupMultiples(Ret, this, Builder, InLoop); if (Next) { Ret = Builder.makeSequence(Ret, Next->Render(Builder, InLoop)); } @@ -455,7 +500,7 @@ void Relooper::Calculate(Block *Entry) { BlockSet JustInner; JustInner.insert(Inner); for (BlockSet::iterator iter = NextEntries.begin(); iter != NextEntries.end(); iter++) { - Solipsize(*iter, Branch::Direct, Simple, JustInner); + Solipsize(*iter, Branch::Break, Simple, JustInner); } } return Simple; @@ -570,6 +615,7 @@ void Relooper::Calculate(Block *Entry) { // Finish up Shape *Inner = Process(InnerBlocks, Entries); Loop->Inner = Inner; + Loop->Entries = Entries; return Loop; } @@ -790,7 +836,8 @@ void Relooper::Calculate(Block *Entry) { 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). + // 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 (BlockBlockSetMap::iterator iter = IndependentGroups.begin(); iter != IndependentGroups.end();) { Block *Entry = iter->first; BlockSet &Group = iter->second; @@ -853,8 +900,18 @@ void Relooper::Calculate(Block *Entry) { if (IndependentGroups.size() > 0) { // Some groups removable ==> Multiple - // checked multiple if prev is not simple (in which case we would be fused) - Make(MakeMultiple(Blocks, *Entries, IndependentGroups, *NextEntries, !(Shape::IsSimple(Prev)))); + // 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 diff --git a/src/cfg/Relooper.h b/src/cfg/Relooper.h index 8ac877d08..50f40fd88 100644 --- a/src/cfg/Relooper.h +++ b/src/cfg/Relooper.h @@ -53,17 +53,21 @@ public: wasm::Binary* makeCheckLabel(wasm::Index value) { return makeBinary(wasm::EqInt32, makeGetLabel(), makeConst(wasm::Literal(int32_t(value)))); } - wasm::Break* makeShapeBreak(int id) { - return wasm::Builder::makeBreak(getBreakName(id)); + + // breaks are on blocks, as they can be specific, we make one wasm block per basic block + wasm::Break* makeBlockBreak(int id) { + return wasm::Builder::makeBreak(getBlockBreakName(id)); } + // continues are on shapes, as there is one per loop, and if we have more than one + // going there, it is irreducible control flow anyhow wasm::Break* makeShapeContinue(int id) { - return wasm::Builder::makeBreak(getContinueName(id)); + return wasm::Builder::makeBreak(getShapeContinueName(id)); } - wasm::Name getBreakName(int id) { - return wasm::Name(std::string("shape$") + std::to_string(id) + "$break"); + wasm::Name getBlockBreakName(int id) { + return wasm::Name(std::string("block$") + std::to_string(id) + "$break"); } - wasm::Name getContinueName(int id) { + wasm::Name getShapeContinueName(int id) { return wasm::Name(std::string("shape$") + std::to_string(id) + "$continue"); } }; @@ -76,9 +80,7 @@ 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 + Continue = 2 }; 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 @@ -144,12 +146,14 @@ struct InsertOrderedSet InsertOrderedSet() {} InsertOrderedSet(const InsertOrderedSet& other) { + *this = other; + } + InsertOrderedSet& operator=(const InsertOrderedSet& other) { + clear(); for (auto i : other.List) { insert(i); // inserting manually creates proper iterators } - } - InsertOrderedSet& operator=(const InsertOrderedSet& other) { - abort(); // TODO, watch out for iterators + return *this; } }; @@ -241,15 +245,20 @@ struct Block { // Represents a structured control flow shape, one of // -// Simple: No control flow at all, just instructions. If several -// blocks, then +// Simple: No control flow at all, just instructions in a single +// basic block. // -// 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. +// Multiple: A shape with at least one entry. We may visit one of +// the entries, or none, before continuing to the next +// shape after this. // -// Loop: An infinite loop. +// Loop: An infinite loop. We assume the property that a loop +// will always visit one of its entries, and so for example +// we cannot have a loop containing a multiple and nothing +// else (since we might not visit any of the multiple's +// blocks). Multiple entries are possible for the block, +// however, which is necessary for irreducible control +// flow, of course. // struct SimpleShape; @@ -285,7 +294,6 @@ struct SimpleShape : public Shape { 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 { @@ -299,6 +307,8 @@ struct MultipleShape : public Shape { struct LoopShape : public Shape { Shape *Inner; + BlockSet Entries; // we must visit at least one of these + LoopShape() : Shape(Loop), Inner(NULL) {} wasm::Expression* Render(RelooperBuilder& Builder, bool InLoop) override; }; |