diff options
Diffstat (limited to 'src/relooper/Relooper.cpp')
| -rw-r--r-- | src/relooper/Relooper.cpp | 445 |
1 files changed, 318 insertions, 127 deletions
diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp index 8c72b0a6..14c203e0 100644 --- a/src/relooper/Relooper.cpp +++ b/src/relooper/Relooper.cpp @@ -1,3 +1,7 @@ +// We are implementing the Relooper C API, so always export from this file. +#ifndef RELOOPERDLL_EXPORTS +#define RELOOPERDLL_EXPORTS +#endif #include "Relooper.h" @@ -6,9 +10,16 @@ #include <list> #include <stack> +#if EMSCRIPTEN #include "ministring.h" +#else +#include <string> +typedef std::string ministring; +#endif -// TODO: move all set to unorderedset +template <class T, class U> bool contains(const T& container, const U& contained) { + return container.find(contained) != container.end(); +} #if DEBUG static void PrintDebug(const char *Format, ...); @@ -18,6 +29,8 @@ static void PrintDebug(const char *Format, ...); #define DebugDump(x, ...) #endif +#define INDENTATION 1 + struct Indenter { static int CurrIndent; @@ -31,27 +44,56 @@ static void PutIndented(const char *String); static char *OutputBufferRoot = NULL; static char *OutputBuffer = NULL; static int OutputBufferSize = 0; +static int OutputBufferOwned = false; + +static int LeftInOutputBuffer() { + return OutputBufferSize - (OutputBuffer - OutputBufferRoot); +} + +static bool EnsureOutputBuffer(int Needed) { // ensures the output buffer is sufficient. returns true is no problem happened + Needed++; // ensure the trailing \0 is not forgotten + int Left = LeftInOutputBuffer(); + if (!OutputBufferOwned) { + assert(Needed < Left); + } else { + // we own the buffer, and can resize if necessary + if (Needed >= Left) { + int Offset = OutputBuffer - OutputBufferRoot; + int TotalNeeded = OutputBufferSize + Needed - Left + 10240; + int NewSize = OutputBufferSize; + while (NewSize < TotalNeeded) NewSize = NewSize + (NewSize/2); + //printf("resize %d => %d\n", OutputBufferSize, NewSize); + OutputBufferRoot = (char*)realloc(OutputBufferRoot, NewSize); + OutputBuffer = OutputBufferRoot + Offset; + OutputBufferSize = NewSize; + return false; + } + } + return true; +} void PrintIndented(const char *Format, ...) { assert(OutputBuffer); - assert(OutputBuffer + Indenter::CurrIndent*2 - OutputBufferRoot < OutputBufferSize); - for (int i = 0; i < Indenter::CurrIndent*2; i++, OutputBuffer++) *OutputBuffer = ' '; - va_list Args; - va_start(Args, Format); - int left = OutputBufferSize - (OutputBuffer - OutputBufferRoot); - int written = vsnprintf(OutputBuffer, left, Format, Args); - assert(written < left); - OutputBuffer += written; - va_end(Args); + EnsureOutputBuffer(Indenter::CurrIndent*INDENTATION); + for (int i = 0; i < Indenter::CurrIndent*INDENTATION; i++, OutputBuffer++) *OutputBuffer = ' '; + int Written; + while (1) { // write and potentially resize buffer until we have enough room + int Left = LeftInOutputBuffer(); + va_list Args; + va_start(Args, Format); + Written = vsnprintf(OutputBuffer, Left, Format, Args); + va_end(Args); + if (EnsureOutputBuffer(Written)) break; + } + OutputBuffer += Written; } void PutIndented(const char *String) { assert(OutputBuffer); - assert(OutputBuffer + Indenter::CurrIndent*2 - OutputBufferRoot < OutputBufferSize); - for (int i = 0; i < Indenter::CurrIndent*2; i++, OutputBuffer++) *OutputBuffer = ' '; - int left = OutputBufferSize - (OutputBuffer - OutputBufferRoot); - int needed = strlen(String)+1; - assert(needed < left); + EnsureOutputBuffer(Indenter::CurrIndent*INDENTATION); + for (int i = 0; i < Indenter::CurrIndent*INDENTATION; i++, OutputBuffer++) *OutputBuffer = ' '; + int Needed = strlen(String)+1; + EnsureOutputBuffer(Needed); strcpy(OutputBuffer, String); OutputBuffer += strlen(String); *OutputBuffer++ = '\n'; @@ -62,15 +104,11 @@ static int AsmJS = 0; // Indenter -#if EMSCRIPTEN int Indenter::CurrIndent = 1; -#else -int Indenter::CurrIndent = 0; -#endif // Branch -Branch::Branch(const char *ConditionInit, const char *CodeInit) : Ancestor(NULL), Labeled(false) { +Branch::Branch(const char *ConditionInit, const char *CodeInit) : Ancestor(NULL), Labeled(true) { Condition = ConditionInit ? strdup(ConditionInit) : NULL; Code = CodeInit ? strdup(CodeInit) : NULL; } @@ -96,14 +134,14 @@ void Branch::Render(Block *Target, bool SetLabel) { // Block -int Block::IdCounter = 1; // 0 is reserved for clearings - -Block::Block(const char *CodeInit) : Parent(NULL), Id(Block::IdCounter++), DefaultTarget(NULL), IsCheckedMultipleEntry(false) { +Block::Block(const char *CodeInit, const char *BranchVarInit) : Parent(NULL), Id(-1), IsCheckedMultipleEntry(false) { Code = strdup(CodeInit); + BranchVar = BranchVarInit ? strdup(BranchVarInit) : NULL; } Block::~Block() { if (Code) free((void*)Code); + if (BranchVar) free((void*)BranchVar); for (BlockBranchMap::iterator iter = ProcessedBranchesOut.begin(); iter != ProcessedBranchesOut.end(); iter++) { delete iter->second; } @@ -111,7 +149,7 @@ Block::~Block() { } void Block::AddBranchTo(Block *Target, const char *Condition, const char *Code) { - assert(BranchesOut.find(Target) == BranchesOut.end()); // cannot add more than one branch to the same target + assert(!contains(BranchesOut, Target)); // cannot add more than one branch to the same target BranchesOut[Target] = new Branch(Condition, Code); } @@ -135,6 +173,7 @@ void Block::Render(bool InLoop) { if (!ProcessedBranchesOut.size()) return; 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 @@ -172,17 +211,25 @@ void Block::Render(bool InLoop) { } } - // We must do this here, because blocks can be split and even comparing their Ids is not enough. We must check the conditions. + Block *DefaultTarget(NULL); // 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); // Must be exactly one default DefaultTarget = iter->first; } } - assert(DefaultTarget); // Must be a default + assert(DefaultTarget); // Since each block *must* branch somewhere, this must be set + + bool useSwitch = BranchVar != NULL; + + if (useSwitch) { + PrintIndented("switch (%s) {\n", BranchVar); + } ministring RemainingConditions; - bool First = true; + bool First = !useSwitch; // when using a switch, there is no special first for (BlockBranchMap::iterator iter = ProcessedBranchesOut.begin();; iter++) { Block *Target; Branch *Details; @@ -195,31 +242,44 @@ void Block::Render(bool InLoop) { Target = DefaultTarget; Details = ProcessedBranchesOut[DefaultTarget]; } - bool SetCurrLabel = SetLabel && Target->IsCheckedMultipleEntry; - bool HasFusedContent = Fused && Fused->InnerMap.find(Target) != Fused->InnerMap.end(); + bool SetCurrLabel = (SetLabel && Target->IsCheckedMultipleEntry) || ForceSetLabel; + bool HasFusedContent = Fused && contains(Fused->InnerMap, Target); bool HasContent = SetCurrLabel || Details->Type != Branch::Direct || HasFusedContent || Details->Code; if (iter != ProcessedBranchesOut.end()) { // If there is nothing to show in this branch, omit the condition - if (HasContent) { - PrintIndented("%sif (%s) {\n", First ? "" : "} else ", Details->Condition); - First = false; + if (useSwitch) { + PrintIndented("%s {\n", Details->Condition); } else { - if (RemainingConditions.size() > 0) RemainingConditions += " && "; - RemainingConditions += "!("; - RemainingConditions += Details->Condition; - RemainingConditions += ")"; + if (HasContent) { + PrintIndented("%sif (%s) {\n", First ? "" : "} else ", Details->Condition); + First = false; + } else { + if (RemainingConditions.size() > 0) RemainingConditions += " && "; + RemainingConditions += "!("; + if (BranchVar) { + RemainingConditions += BranchVar; + RemainingConditions += " == "; + } + RemainingConditions += Details->Condition; + RemainingConditions += ")"; + } } } else { - if (HasContent) { - if (RemainingConditions.size() > 0) { - if (First) { - PrintIndented("if (%s) {\n", RemainingConditions.c_str()); - First = false; - } else { - PrintIndented("} else if (%s) {\n", RemainingConditions.c_str()); + // this is the default + if (useSwitch) { + PrintIndented("default: {\n"); + } else { + if (HasContent) { + if (RemainingConditions.size() > 0) { + if (First) { + PrintIndented("if (%s) {\n", RemainingConditions.c_str()); + First = false; + } else { + PrintIndented("} else if (%s) {\n", RemainingConditions.c_str()); + } + } else if (!First) { + PrintIndented("} else {\n"); } - } else if (!First) { - PrintIndented("} else {\n"); } } } @@ -228,7 +288,13 @@ void Block::Render(bool InLoop) { if (HasFusedContent) { Fused->InnerMap.find(Target)->second->Render(InLoop); } + if (useSwitch && iter != ProcessedBranchesOut.end()) { + PrintIndented("break;\n"); + } if (!First) Indenter::Unindent(); + if (useSwitch) { + PrintIndented("}\n"); + } if (iter == ProcessedBranchesOut.end()) break; } if (!First) PrintIndented("}\n"); @@ -238,10 +304,6 @@ void Block::Render(bool InLoop) { } } -// Shape - -int Shape::IdCounter = 0; - // MultipleShape void MultipleShape::RenderLoopPrefix() { @@ -264,12 +326,26 @@ void MultipleShape::RenderLoopPostfix() { void MultipleShape::Render(bool InLoop) { RenderLoopPrefix(); - bool First = true; + + // We know that blocks with the same Id were split from the same source, so their contents are identical and they are logically the same, so re-merge them here + typedef std::map<int, Shape*> IdShapeMap; + IdShapeMap IdMap; for (BlockShapeMap::iterator iter = InnerMap.begin(); iter != InnerMap.end(); iter++) { + int Id = iter->first->Id; + IdShapeMap::iterator Test = IdMap.find(Id); + if (Test != IdMap.end()) { + assert(Shape::IsSimple(iter->second) && Shape::IsSimple(Test->second)); // we can only merge simple blocks, something horrible has gone wrong if we see anything else + continue; + } + IdMap[iter->first->Id] = iter->second; + } + + bool First = true; + for (IdShapeMap::iterator iter = IdMap.begin(); iter != IdMap.end(); iter++) { if (AsmJS) { - PrintIndented("%sif ((label|0) == %d) {\n", First ? "" : "else ", iter->first->Id); + PrintIndented("%sif ((label|0) == %d) {\n", First ? "" : "else ", iter->first); } else { - PrintIndented("%sif (label == %d) {\n", First ? "" : "else ", iter->first->Id); + PrintIndented("%sif (label == %d) {\n", First ? "" : "else ", iter->first); } First = false; Indenter::Indent(); @@ -279,7 +355,7 @@ void MultipleShape::Render(bool InLoop) { } RenderLoopPostfix(); if (Next) Next->Render(InLoop); -}; +} // LoopShape @@ -294,18 +370,21 @@ void LoopShape::Render(bool InLoop) { Indenter::Unindent(); PrintIndented("}\n"); if (Next) Next->Render(InLoop); -}; +} -/* // EmulatedShape void EmulatedShape::Render(bool InLoop) { + PrintIndented("label = %d;\n", Entry->Id); + if (Labeled) { + PrintIndented("L%d: ", Id); + } PrintIndented("while(1) {\n"); Indenter::Indent(); - PrintIndented("switch(label) {\n"); + PrintIndented("switch(label|0) {\n"); Indenter::Indent(); - for (int i = 0; i < Blocks.size(); i++) { - Block *Curr = Blocks[i]; + for (BlockSet::iterator iter = Blocks.begin(); iter != Blocks.end(); iter++) { + Block *Curr = *iter; PrintIndented("case %d: {\n", Curr->Id); Indenter::Indent(); Curr->Render(InLoop); @@ -318,20 +397,20 @@ void EmulatedShape::Render(bool InLoop) { Indenter::Unindent(); PrintIndented("}\n"); if (Next) Next->Render(InLoop); -}; -*/ +} // Relooper -Relooper::Relooper() : Root(NULL) { +Relooper::Relooper() : Root(NULL), Emulate(false), BlockIdCounter(1), ShapeIdCounter(0) { // block ID 0 is reserved for clearings } Relooper::~Relooper() { - for (int i = 0; i < Blocks.size(); i++) delete Blocks[i]; - for (int i = 0; i < Shapes.size(); i++) delete Shapes[i]; + 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) { +void Relooper::AddBlock(Block *New, int Id) { + New->Id = Id == -1 ? BlockIdCounter++ : Id; Blocks.push_back(New); } @@ -354,7 +433,7 @@ void Relooper::Calculate(Block *Entry) { while (ToInvestigate.size() > 0) { Block *Curr = ToInvestigate.front(); ToInvestigate.pop_front(); - if (Live.find(Curr) != Live.end()) continue; + 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); @@ -367,7 +446,7 @@ void Relooper::Calculate(Block *Entry) { // RAII cleanup. Without splitting, we will be forced to introduce labelled loops to allow // reaching the final block void SplitDeadEnds() { - int TotalCodeSize = 0; + unsigned TotalCodeSize = 0; for (BlockSet::iterator iter = Live.begin(); iter != Live.end(); iter++) { Block *Curr = *iter; TotalCodeSize += strlen(Curr->Code); @@ -378,15 +457,14 @@ void Relooper::Calculate(Block *Entry) { for (BlockSet::iterator iter = Live.begin(); iter != Live.end(); iter++) { Block *Original = *iter; if (Original->BranchesIn.size() <= 1 || Original->BranchesOut.size() > 0) continue; // only dead ends, for now - if (Original->BranchesOut.find(Original) != Original->BranchesOut.end()) continue; // cannot split a looping node + if (contains(Original->BranchesOut, Original)) continue; // cannot split a looping node if (strlen(Original->Code)*(Original->BranchesIn.size()-1) > TotalCodeSize/5) continue; // if splitting increases raw code size by a significant amount, abort // Split the node (for simplicity, we replace all the blocks, even though we could have reused the original) PrintDebug("Splitting block %d\n", Original->Id); for (BlockSet::iterator iter = Original->BranchesIn.begin(); iter != Original->BranchesIn.end(); iter++) { Block *Prior = *iter; - Block *Split = new Block(Original->Code); - Parent->Blocks.push_back(Split); - PrintDebug(" to %d\n", Split->Id); + Block *Split = new Block(Original->Code, Original->BranchVar); + Parent->AddBlock(Split, Original->Id); Split->BranchesIn.insert(Prior); Branch *Details = Prior->BranchesOut[Original]; Prior->BranchesOut[Split] = new Branch(Details->Condition, Details->Code); @@ -419,15 +497,15 @@ void Relooper::Calculate(Block *Entry) { Pre.FindLive(Entry); // Add incoming branches from live blocks, ignoring dead code - for (int i = 0; i < Blocks.size(); i++) { + for (unsigned i = 0; i < Blocks.size(); i++) { Block *Curr = Blocks[i]; - if (Pre.Live.find(Curr) == Pre.Live.end()) continue; + if (!contains(Pre.Live, Curr)) continue; for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { iter->first->BranchesIn.insert(Curr); } } - Pre.SplitDeadEnds(); + if (!Emulate) Pre.SplitDeadEnds(); // Recursively process the graph @@ -436,6 +514,7 @@ void Relooper::Calculate(Block *Entry) { // 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); } @@ -443,7 +522,7 @@ void Relooper::Calculate(Block *Entry) { // will appear void GetBlocksOut(Block *Source, BlockSet& Entries, BlockSet *LimitTo=NULL) { for (BlockBranchMap::iterator iter = Source->BranchesOut.begin(); iter != Source->BranchesOut.end(); iter++) { - if (!LimitTo || LimitTo->find(iter->first) != LimitTo->end()) { + if (!LimitTo || contains(*LimitTo, iter->first)) { Entries.insert(iter->first); } } @@ -455,7 +534,7 @@ void Relooper::Calculate(Block *Entry) { DebugDump(From, " relevant to solipsize: "); for (BlockSet::iterator iter = Target->BranchesIn.begin(); iter != Target->BranchesIn.end();) { Block *Prior = *iter; - if (From.find(Prior) == From.end()) { + if (!contains(From, Prior)) { iter++; continue; } @@ -492,6 +571,21 @@ void Relooper::Calculate(Block *Entry) { 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. @@ -500,7 +594,7 @@ void Relooper::Calculate(Block *Entry) { while (Queue.size() > 0) { Block *Curr = *(Queue.begin()); Queue.erase(Queue.begin()); - if (InnerBlocks.find(Curr) == InnerBlocks.end()) { + if (!contains(InnerBlocks, Curr)) { // This element is new, mark it as inner and remove from outer InnerBlocks.insert(Curr); Blocks.erase(Curr); @@ -508,6 +602,16 @@ void Relooper::Calculate(Block *Entry) { 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); @@ -516,20 +620,66 @@ void Relooper::Calculate(Block *Entry) { Block *Curr = *iter; for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { Block *Possible = iter->first; - if (InnerBlocks.find(Possible) == InnerBlocks.end()) { + 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 = NULL; + 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 (Hoisted.find(Target) == Hoisted.end() && NextEntries.find(Target) == NextEntries.end()) { + // 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"); DebugDump(InnerBlocks, " inner blocks:"); DebugDump(Entries, " inner entries:"); DebugDump(Blocks, " outer blocks:"); DebugDump(NextEntries, " outer entries:"); - // TODO: Optionally hoist additional blocks into the loop - LoopShape *Loop = new LoopShape(); Notice(Loop); @@ -551,7 +701,8 @@ void Relooper::Calculate(Block *Entry) { // 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. - void FindIndependentGroups(BlockSet &Blocks, BlockSet &Entries, BlockBlockSetMap& IndependentGroups) { + // @param Ignore - previous blocks that are irrelevant + void FindIndependentGroups(BlockSet &Entries, BlockBlockSetMap& IndependentGroups, BlockSet *Ignore=NULL) { typedef std::map<Block*, Block*> BlockBlockMap; struct HelperClass { @@ -566,7 +717,7 @@ void Relooper::Calculate(Block *Entry) { Block *Invalidatee = ToInvalidate.front(); ToInvalidate.pop_front(); Block *Owner = Ownership[Invalidatee]; - if (IndependentGroups.find(Owner) != IndependentGroups.end()) { // Owner may have been invalidated, do not add to IndependentGroups! + 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 @@ -639,6 +790,7 @@ void Relooper::Calculate(Block *Entry) { 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); } @@ -689,7 +841,7 @@ void Relooper::Calculate(Block *Entry) { Block *CurrTarget = iter->first; BlockBranchMap::iterator Next = iter; Next++; - if (CurrBlocks.find(CurrTarget) == CurrBlocks.end()) { + if (!contains(CurrBlocks, CurrTarget)) { NextEntries.insert(CurrTarget); Solipsize(CurrTarget, Branch::Break, Multiple, CurrBlocks); } @@ -706,7 +858,7 @@ void Relooper::Calculate(Block *Entry) { // Add entries not handled as next entries, they are deferred for (BlockSet::iterator iter = Entries.begin(); iter != Entries.end(); iter++) { Block *Entry = *iter; - if (IndependentGroups.find(Entry) == IndependentGroups.end()) { + if (!contains(IndependentGroups, Entry)) { NextEntries.insert(Entry); } } @@ -745,6 +897,9 @@ void Relooper::Calculate(Block *Entry) { 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)); @@ -752,11 +907,12 @@ void Relooper::Calculate(Block *Entry) { // 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(Blocks, *Entries, IndependentGroups); + FindIndependentGroups(*Entries, IndependentGroups); PrintDebug("Independent groups: %d\n", IndependentGroups.size()); @@ -770,7 +926,7 @@ void Relooper::Calculate(Block *Entry) { 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 (Group.find(Origin) == Group.end()) { + 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); @@ -808,7 +964,7 @@ void Relooper::Calculate(Block *Entry) { Block *Curr = *iter; for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { Block *Target = iter->first; - if (SmallGroup.find(Target) == SmallGroup.end()) { + if (!contains(SmallGroup, Target)) { DeadEnd = false; break; } @@ -849,6 +1005,7 @@ void Relooper::Calculate(Block *Entry) { BlockSet Entries; Entries.insert(Entry); Root = Analyzer(this).Process(AllBlocks, Entries, NULL); + assert(Root); // Post optimizations @@ -858,13 +1015,13 @@ void Relooper::Calculate(Block *Entry) { PostOptimizer(Relooper *ParentInit) : Parent(ParentInit), Closure(NULL) {} - #define RECURSE_MULTIPLE_MANUAL(func, manual) \ - for (BlockShapeMap::iterator iter = manual->InnerMap.begin(); iter != manual->InnerMap.end(); iter++) { \ + #define RECURSE_Multiple(shape, func) \ + for (BlockShapeMap::iterator iter = shape->InnerMap.begin(); iter != shape->InnerMap.end(); iter++) { \ func(iter->second); \ } - #define RECURSE_MULTIPLE(func) RECURSE_MULTIPLE_MANUAL(func, Multiple); - #define RECURSE_LOOP(func) \ - func(Loop->Inner); + #define RECURSE_Loop(shape, func) \ + func(shape->Inner); + #define RECURSE(shape, func) RECURSE_##shape(shape, func); #define SHAPE_SWITCH(var, simple, multiple, loop) \ if (SimpleShape *Simple = Shape::IsSimple(var)) { \ @@ -875,20 +1032,6 @@ void Relooper::Calculate(Block *Entry) { loop; \ } - #define SHAPE_SWITCH_AUTO(var, simple, multiple, loop, func) \ - if (SimpleShape *Simple = Shape::IsSimple(var)) { \ - simple; \ - func(Simple->Next); \ - } else if (MultipleShape *Multiple = Shape::IsMultiple(var)) { \ - multiple; \ - RECURSE_MULTIPLE(func) \ - func(Multiple->Next); \ - } else if (LoopShape *Loop = Shape::IsLoop(var)) { \ - loop; \ - RECURSE_LOOP(func); \ - func(Loop->Next); \ - } - // Find the blocks that natural control flow can get us directly to, or through a multiple that we ignore void FollowNaturalFlow(Shape *S, BlockSet &Out) { SHAPE_SWITCH(S, { @@ -903,10 +1046,28 @@ void Relooper::Calculate(Block *Entry) { }); } + void FindNaturals(Shape *Root, Shape *Otherwise=NULL) { + if (Root->Next) { + Root->Natural = Root->Next; + FindNaturals(Root->Next, Otherwise); + } else { + Root->Natural = Otherwise; + } + + SHAPE_SWITCH(Root, { + }, { + for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) { + FindNaturals(iter->second, Root->Natural); + } + }, { + FindNaturals(Loop->Inner, Loop->Inner); + }); + } + // Remove unneeded breaks and continues. // A flow operation is trivially unneeded if the shape we naturally get to by normal code // execution is the same as the flow forces us to. - void RemoveUnneededFlows(Shape *Root, Shape *Natural=NULL) { + void RemoveUnneededFlows(Shape *Root, Shape *Natural=NULL, LoopShape *LastLoop=NULL) { BlockSet NaturalBlocks; FollowNaturalFlow(Natural, NaturalBlocks); Shape *Next = Root; @@ -914,6 +1075,8 @@ void Relooper::Calculate(Block *Entry) { Root = Next; Next = NULL; SHAPE_SWITCH(Root, { + if (Simple->Inner->BranchVar) LastLoop = NULL; // a switch clears out the loop (TODO: only for breaks, not continue) + // If there is a next block, we already know at Simple creation time to make direct branches, // and we can do nothing more. If there is no next however, then Natural is where we will // go to by doing nothing, so we can potentially optimize some branches to direct. @@ -923,21 +1086,27 @@ void Relooper::Calculate(Block *Entry) { for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) { Block *Target = iter->first; Branch *Details = iter->second; - if (Details->Type != Branch::Direct && NaturalBlocks.find(Target) != NaturalBlocks.end()) { // note: cannot handle split blocks + if (Details->Type != Branch::Direct && contains(NaturalBlocks, Target)) { // note: cannot handle split blocks Details->Type = Branch::Direct; if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) { Multiple->NeedLoop--; } + } else if (Details->Type == Branch::Break && LastLoop && LastLoop->Natural == Details->Ancestor->Natural) { + // it is important to simplify breaks, as simpler breaks enable other optimizations + Details->Labeled = false; + if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) { + Multiple->NeedLoop--; + } } } } }, { for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) { - RemoveUnneededFlows(iter->second, Multiple->Next); + RemoveUnneededFlows(iter->second, Multiple->Next, Multiple->NeedLoop ? NULL : LastLoop); } Next = Multiple->Next; }, { - RemoveUnneededFlows(Loop->Inner, Loop->Inner); + RemoveUnneededFlows(Loop->Inner, Loop->Inner, Loop); Next = Loop->Next; }); } @@ -961,24 +1130,33 @@ void Relooper::Calculate(Block *Entry) { // If we are fusing a Multiple with a loop into this Simple, then visit it now if (Fused && Fused->NeedLoop) { LoopStack.push(Fused); - RECURSE_MULTIPLE_MANUAL(FindLabeledLoops, Fused); + } + if (Simple->Inner->BranchVar) { + LoopStack.push(NULL); // a switch means breaks are now useless, push a dummy + } + if (Fused) { + RECURSE_Multiple(Fused, FindLabeledLoops); } for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) { Block *Target = iter->first; Branch *Details = iter->second; if (Details->Type != Branch::Direct) { assert(LoopStack.size() > 0); - if (Details->Ancestor != LoopStack.top()) { + if (Details->Ancestor != LoopStack.top() && Details->Labeled) { LabeledShape *Labeled = Shape::IsLabeled(Details->Ancestor); Labeled->Labeled = true; - Details->Labeled = true; } else { Details->Labeled = false; } } } + if (Simple->Inner->BranchVar) { + LoopStack.pop(); + } if (Fused && Fused->NeedLoop) { LoopStack.pop(); + } + if (Fused) { Next = Fused->Next; } else { Next = Root->Next; @@ -987,14 +1165,14 @@ void Relooper::Calculate(Block *Entry) { if (Multiple->NeedLoop) { LoopStack.push(Multiple); } - RECURSE_MULTIPLE(FindLabeledLoops); + RECURSE(Multiple, FindLabeledLoops); if (Multiple->NeedLoop) { LoopStack.pop(); } Next = Root->Next; }, { LoopStack.push(Loop); - RECURSE_LOOP(FindLabeledLoops); + RECURSE(Loop, FindLabeledLoops); LoopStack.pop(); Next = Root->Next; }); @@ -1006,6 +1184,7 @@ void Relooper::Calculate(Block *Entry) { } void Process(Shape *Root) { + FindNaturals(Root); RemoveUnneededFlows(Root); FindLabeledLoops(Root); } @@ -1018,17 +1197,25 @@ void Relooper::Calculate(Block *Entry) { void Relooper::Render() { OutputBuffer = OutputBufferRoot; + assert(Root); Root->Render(false); } void Relooper::SetOutputBuffer(char *Buffer, int Size) { OutputBufferRoot = OutputBuffer = Buffer; OutputBufferSize = Size; + OutputBufferOwned = false; } void Relooper::MakeOutputBuffer(int Size) { + if (OutputBufferRoot && OutputBufferSize >= Size && OutputBufferOwned) return; OutputBufferRoot = OutputBuffer = (char*)malloc(Size); OutputBufferSize = Size; + OutputBufferOwned = true; +} + +char *Relooper::GetOutputBuffer() { + return OutputBufferRoot; } void Relooper::SetAsmJSMode(int On) { @@ -1046,13 +1233,17 @@ void Debugging::Dump(BlockSet &Blocks, const char *prefix) { for (BlockBranchMap::iterator iter2 = Curr->BranchesOut.begin(); iter2 != Curr->BranchesOut.end(); iter2++) { Block *Other = iter2->first; printf(" -> %d\n", Other->Id); - assert(Other->BranchesIn.find(Curr) != Other->BranchesIn.end()); + 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); SHAPE_SWITCH(S, { printf("<< Simple with block %d\n", Simple->Inner->Id); @@ -1082,7 +1273,7 @@ VoidIntMap __blockDebugMap__; // maps block pointers in currently running code t extern "C" { -void rl_set_output_buffer(char *buffer, int size) { +RELOOPERDLL_API void rl_set_output_buffer(char *buffer, int size) { #if DEBUG printf("#include \"Relooper.h\"\n"); printf("int main() {\n"); @@ -1092,16 +1283,16 @@ void rl_set_output_buffer(char *buffer, int size) { Relooper::SetOutputBuffer(buffer, size); } -void rl_make_output_buffer(int size) { +RELOOPERDLL_API void rl_make_output_buffer(int size) { Relooper::SetOutputBuffer((char*)malloc(size), size); } -void rl_set_asm_js_mode(int on) { +RELOOPERDLL_API void rl_set_asm_js_mode(int on) { Relooper::SetAsmJSMode(on); } -void *rl_new_block(const char *text) { - Block *ret = new Block(text); +RELOOPERDLL_API void *rl_new_block(const char *text, const char *branch_var) { + Block *ret = new Block(text, branch_var); #if DEBUG printf(" void *b%d = rl_new_block(\"// code %d\");\n", ret->Id, ret->Id); __blockDebugMap__[ret] = ret->Id; @@ -1110,21 +1301,21 @@ void *rl_new_block(const char *text) { return ret; } -void rl_delete_block(void *block) { +RELOOPERDLL_API void rl_delete_block(void *block) { #if DEBUG printf(" rl_delete_block(block_map[%d]);\n", ((Block*)block)->Id); #endif delete (Block*)block; } -void rl_block_add_branch_to(void *from, void *to, const char *condition, const char *code) { +RELOOPERDLL_API void rl_block_add_branch_to(voi |