From 3634b45c63e420910c77a631352ab257b8a6039f Mon Sep 17 00:00:00 2001 From: Alon Zakai Date: Sun, 11 Nov 2012 10:04:33 -0800 Subject: add relooper sources --- src/relooper/README.markdown | 14 + src/relooper/Relooper.cpp | 1038 ++++++++++++++++++++++++++++++++++++++ src/relooper/Relooper.h | 246 +++++++++ src/relooper/doit.sh | 68 +++ src/relooper/emscripten/Makefile | 18 + src/relooper/emscripten/glue.js | 54 ++ src/relooper/emscripten/test.js | 44 ++ src/relooper/fuzzer.py | 116 +++++ src/relooper/ministring.h | 35 ++ src/relooper/paper.pdf | Bin 0 -> 220318 bytes src/relooper/test.cpp | 195 +++++++ src/relooper/test.txt | 99 ++++ src/relooper/test2.c | 44 ++ src/relooper/test2.txt | 12 + src/relooper/test3.c | 42 ++ src/relooper/test3.txt | 27 + src/relooper/test4.cpp | 40 ++ src/relooper/test4.txt | 24 + src/relooper/test5.cpp | 40 ++ src/relooper/test5.txt | 32 ++ src/relooper/test6.cpp | 31 ++ src/relooper/test6.txt | 12 + src/relooper/test_dead.cpp | 28 + src/relooper/test_dead.txt | 9 + src/relooper/test_debug.cpp | 30 ++ src/relooper/test_debug.txt | 96 ++++ src/relooper/test_fuzz1.cpp | 52 ++ src/relooper/test_fuzz1.txt | 44 ++ src/relooper/test_fuzz2.cpp | 34 ++ src/relooper/test_fuzz2.txt | 14 + src/relooper/test_fuzz3.cpp | 36 ++ src/relooper/test_fuzz3.txt | 9 + src/relooper/test_fuzz4.cpp | 38 ++ src/relooper/test_fuzz4.txt | 20 + src/relooper/test_fuzz5.cpp | 57 +++ src/relooper/test_fuzz5.txt | 56 ++ src/relooper/test_fuzz6.cpp | 322 ++++++++++++ src/relooper/test_fuzz6.txt | 116 +++++ src/relooper/test_inf.cpp | 813 +++++++++++++++++++++++++++++ src/relooper/test_inf.txt | 392 ++++++++++++++ src/relooper/testit.sh | 60 +++ src/relooper/updateit.sh | 16 + 42 files changed, 4473 insertions(+) create mode 100644 src/relooper/README.markdown create mode 100644 src/relooper/Relooper.cpp create mode 100644 src/relooper/Relooper.h create mode 100755 src/relooper/doit.sh create mode 100644 src/relooper/emscripten/Makefile create mode 100644 src/relooper/emscripten/glue.js create mode 100644 src/relooper/emscripten/test.js create mode 100644 src/relooper/fuzzer.py create mode 100644 src/relooper/ministring.h create mode 100644 src/relooper/paper.pdf create mode 100644 src/relooper/test.cpp create mode 100644 src/relooper/test.txt create mode 100644 src/relooper/test2.c create mode 100644 src/relooper/test2.txt create mode 100644 src/relooper/test3.c create mode 100644 src/relooper/test3.txt create mode 100644 src/relooper/test4.cpp create mode 100644 src/relooper/test4.txt create mode 100644 src/relooper/test5.cpp create mode 100644 src/relooper/test5.txt create mode 100644 src/relooper/test6.cpp create mode 100644 src/relooper/test6.txt create mode 100644 src/relooper/test_dead.cpp create mode 100644 src/relooper/test_dead.txt create mode 100644 src/relooper/test_debug.cpp create mode 100644 src/relooper/test_debug.txt create mode 100644 src/relooper/test_fuzz1.cpp create mode 100644 src/relooper/test_fuzz1.txt create mode 100644 src/relooper/test_fuzz2.cpp create mode 100644 src/relooper/test_fuzz2.txt create mode 100644 src/relooper/test_fuzz3.cpp create mode 100644 src/relooper/test_fuzz3.txt create mode 100644 src/relooper/test_fuzz4.cpp create mode 100644 src/relooper/test_fuzz4.txt create mode 100644 src/relooper/test_fuzz5.cpp create mode 100644 src/relooper/test_fuzz5.txt create mode 100644 src/relooper/test_fuzz6.cpp create mode 100644 src/relooper/test_fuzz6.txt create mode 100644 src/relooper/test_inf.cpp create mode 100644 src/relooper/test_inf.txt create mode 100755 src/relooper/testit.sh create mode 100755 src/relooper/updateit.sh diff --git a/src/relooper/README.markdown b/src/relooper/README.markdown new file mode 100644 index 00000000..9b0187b3 --- /dev/null +++ b/src/relooper/README.markdown @@ -0,0 +1,14 @@ + +Relooper +======== + +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] - see paper.pdf - was published +about it, and is written in an LLVM-friendly way with the goal of inclusion +in upstream LLVM. + +License: MIT&LLVM + +[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 + diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp new file mode 100644 index 00000000..f16055c0 --- /dev/null +++ b/src/relooper/Relooper.cpp @@ -0,0 +1,1038 @@ + +#include "Relooper.h" + +#include +#include +#include +#include + +#include "ministring.h" + +// TODO: move all set to unorderedset + +#if DEBUG +static void PrintDebug(const char *Format, ...); +#define DebugDump(x, ...) Debugging::Dump(x, __VA_ARGS__) +#else +#define PrintDebug(x, ...) +#define DebugDump(x, ...) +#endif + +struct Indenter { + static int CurrIndent; + + static void Indent() { CurrIndent++; } + static void Unindent() { CurrIndent--; } +}; + +static void PrintIndented(const char *Format, ...); +static void PutIndented(const char *String); + +static char *OutputBufferRoot = NULL; +static char *OutputBuffer = NULL; +static int OutputBufferSize = 0; + +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); +} + +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); + strcpy(OutputBuffer, String); + OutputBuffer += strlen(String); + *OutputBuffer++ = '\n'; + *OutputBuffer = 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) { + Condition = ConditionInit ? strdup(ConditionInit) : NULL; + Code = CodeInit ? strdup(CodeInit) : NULL; +} + +Branch::~Branch() { + if (Condition) free((void*)Condition); + if (Code) free((void*)Code); +} + +void Branch::Render(Block *Target, bool SetLabel) { + if (Code) PrintIndented("%s\n", Code); + if (SetLabel) PrintIndented("label = %d;\n", Target->Id); + if (Ancestor) { + if (Type != Direct) { + if (Labeled) { + PrintIndented("%s L%d;\n", Type == Break ? "break" : "continue", Ancestor->Id); + } else { + PrintIndented("%s;\n", Type == Break ? "break" : "continue"); + } + } + } +} + +// Block + +int Block::IdCounter = 1; // 0 is reserved for clearings + +Block::Block(const char *CodeInit) : Parent(NULL), Id(Block::IdCounter++), DefaultTarget(NULL), IsCheckedMultipleEntry(false) { + Code = strdup(CodeInit); +} + +Block::~Block() { + if (Code) free((void*)Code); + for (BlockBranchMap::iterator iter = ProcessedBranchesIn.begin(); iter != ProcessedBranchesIn.end(); iter++) { + delete iter->second; + } + for (BlockBranchMap::iterator iter = ProcessedBranchesOut.begin(); iter != ProcessedBranchesOut.end(); iter++) { + delete iter->second; + } + // XXX If not reachable, expected to have branches here. But need to clean them up to prevent leaks! +} + +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 + BranchesOut[Target] = new Branch(Condition, Code); +} + +void Block::Render(bool InLoop) { + if (IsCheckedMultipleEntry && InLoop) { + PrintIndented("label = 0;\n"); + } + + if (Code) { + // Print code in an indented manner, even over multiple lines + char *Start = const_cast(Code); + while (*Start) { + char *End = strchr(Start, '\n'); + if (End) *End = 0; + PutIndented(Start); + if (End) *End = '\n'; else break; + Start = End+1; + } + } + + if (!ProcessedBranchesOut.size()) return; + + bool SetLabel = true; // in some cases it is clear we can avoid setting label, see later + + if (ProcessedBranchesOut.size() == 1 && ProcessedBranchesOut.begin()->second->Type == Branch::Direct) { + SetLabel = false; + } + + // 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"); + Parent->Next = Parent->Next->Next; + Fused->RenderLoopPrefix(); + + // 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; + } + } + + // We must do this here, because blocks can be split and even comparing their Ids is not enough. We must check the conditions. + 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 + + ministring RemainingConditions; + bool First = true; + 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; + bool HasFusedContent = Fused && Fused->InnerMap.find(Target) != Fused->InnerMap.end(); + 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; + } else { + if (RemainingConditions.size() > 0) RemainingConditions += " && "; + 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()); + } + } else if (!First) { + PrintIndented("} else {\n"); + } + } + } + if (!First) Indenter::Indent(); + Details->Render(Target, SetCurrLabel); + if (HasFusedContent) { + Fused->InnerMap.find(Target)->second->Render(InLoop); + } + if (!First) Indenter::Unindent(); + if (iter == ProcessedBranchesOut.end()) break; + } + if (!First) PrintIndented("}\n"); + + if (Fused) { + Fused->RenderLoopPostfix(); + } +} + +// Shape + +int Shape::IdCounter = 0; + +// MultipleShape + +void MultipleShape::RenderLoopPrefix() { + if (NeedLoop) { + if (Labeled) { + PrintIndented("L%d: do {\n", Id); + } else { + PrintIndented("do {\n"); + } + Indenter::Indent(); + } +} + +void MultipleShape::RenderLoopPostfix() { + if (NeedLoop) { + Indenter::Unindent(); + PrintIndented("} while(0);\n"); + } +} + +void MultipleShape::Render(bool InLoop) { + RenderLoopPrefix(); + bool First = true; + for (BlockShapeMap::iterator iter = InnerMap.begin(); iter != InnerMap.end(); iter++) { + PrintIndented("%sif (label == %d) {\n", First ? "" : "else ", iter->first->Id); + First = false; + Indenter::Indent(); + iter->second->Render(InLoop); + Indenter::Unindent(); + PrintIndented("}\n"); + } + RenderLoopPostfix(); + if (Next) Next->Render(InLoop); +}; + +// LoopShape + +void LoopShape::Render(bool InLoop) { + if (Labeled) { + PrintIndented("L%d: while(1) {\n", Id); + } else { + PrintIndented("while(1) {\n"); + } + Indenter::Indent(); + Inner->Render(true); + Indenter::Unindent(); + PrintIndented("}\n"); + if (Next) Next->Render(InLoop); +}; + +/* +// EmulatedShape + +void EmulatedShape::Render(bool InLoop) { + PrintIndented("while(1) {\n"); + Indenter::Indent(); + PrintIndented("switch(label) {\n"); + Indenter::Indent(); + for (int i = 0; i < Blocks.size(); i++) { + Block *Curr = Blocks[i]; + PrintIndented("case %d: {\n", Curr->Id); + Indenter::Indent(); + Curr->Render(InLoop); + PrintIndented("break;\n"); + Indenter::Unindent(); + PrintIndented("}\n"); + } + Indenter::Unindent(); + PrintIndented("}\n"); + Indenter::Unindent(); + PrintIndented("}\n"); + if (Next) Next->Render(InLoop); +}; +*/ + +// Relooper + +Relooper::Relooper() : Root(NULL) { +} + +Relooper::~Relooper() { + for (int i = 0; i < Blocks.size(); i++) delete Blocks[i]; + for (int i = 0; i < Shapes.size(); i++) delete Shapes[i]; +} + +void Relooper::AddBlock(Block *New) { + Blocks.push_back(New); +} + +struct RelooperRecursor { + Relooper *Parent; + RelooperRecursor(Relooper *ParentInit) : Parent(ParentInit) {} +}; + +void Relooper::Calculate(Block *Entry) { + // Scan and optimize the input + struct PreOptimizer : public RelooperRecursor { + PreOptimizer(Relooper *Parent) : RelooperRecursor(Parent) {} + BlockSet Live; + + void FindLive(Block *Curr) { + if (Live.find(Curr) != Live.end()) return; + Live.insert(Curr); + for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { + FindLive(iter->first); + } + } + + // If a block has multiple entries but no exits, and it is small enough, it is useful to split it. + // A common example is a C++ function where everything ends up at a final exit block and does some + // RAII cleanup. Without splitting, we will be forced to introduce labelled loops to allow + // reaching the final block + void SplitDeadEnds() { + int TotalCodeSize = 0; + for (BlockSet::iterator iter = Live.begin(); iter != Live.end(); iter++) { + Block *Curr = *iter; + TotalCodeSize += strlen(Curr->Code); + } + + for (BlockSet::iterator iter = Live.begin(); iter != Live.end(); iter++) { + Block *Original = *iter; + if (Original->BranchesIn.size() <= 1 || Original->BranchesOut.size() > 0) continue; + 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) + for (BlockBranchMap::iterator iter = Original->BranchesIn.begin(); iter != Original->BranchesIn.end(); iter++) { + Block *Prior = iter->first; + Block *Split = new Block(Original->Code); + Split->BranchesIn[Prior] = new Branch(NULL); + Prior->BranchesOut[Split] = new Branch(Prior->BranchesOut[Original]->Condition, Prior->BranchesOut[Original]->Code); + Prior->BranchesOut.erase(Original); + Parent->AddBlock(Split); + Live.insert(Split); + } + } + } + }; + PreOptimizer Pre(this); + Pre.FindLive(Entry); + + // Add incoming branches from live blocks, ignoring dead code + for (int i = 0; i < Blocks.size(); i++) { + Block *Curr = Blocks[i]; + if (Pre.Live.find(Curr) == Pre.Live.end()) continue; + for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) { + iter->first->BranchesIn[Curr] = new Branch(NULL); + } + } + + Pre.SplitDeadEnds(); + + // 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) { + 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=NULL) { + for (BlockBranchMap::iterator iter = Source->BranchesOut.begin(); iter != Source->BranchesOut.end(); iter++) { + if (!LimitTo || LimitTo->find(iter->first) != LimitTo->end()) { + 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 (BlockBranchMap::iterator iter = Target->BranchesIn.begin(); iter != Target->BranchesIn.end();) { + Block *Prior = iter->first; + if (From.find(Prior) == From.end()) { + iter++; + continue; + } + Branch *TargetIn = iter->second; + Branch *PriorOut = Prior->BranchesOut[Target]; + PriorOut->Ancestor = Ancestor; // Do we need this info + PriorOut->Type = Type; // on TargetIn too? + if (MultipleShape *Multiple = Shape::IsMultiple(Ancestor)) { + Multiple->NeedLoop++; // We are breaking out of this Multiple, so need a loop + } + iter++; // carefully increment iter before erasing + Target->BranchesIn.erase(Prior); + Target->ProcessedBranchesIn[Prior] = TargetIn; + 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 *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 (InnerBlocks.find(Curr) == InnerBlocks.end()) { + // 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 (BlockBranchMap::iterator iter = Curr->BranchesIn.begin(); iter != Curr->BranchesIn.end(); iter++) { + Queue.insert(iter->first); + } + } + } + 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 (InnerBlocks.find(Possible) == InnerBlocks.end() && + NextEntries.find(Possible) == NextEntries.find(Possible)) { + NextEntries.insert(Possible); + } + } + } + + 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); + + // 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, NULL); + 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. + void FindIndependentGroups(BlockSet &Blocks, BlockSet &Entries, BlockBlockSetMap& IndependentGroups) { + typedef std::map BlockBlockMap; + typedef std::list BlockList; + + 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 (IndependentGroups.find(Owner) != IndependentGroups.end()) { // 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] = NULL; + 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 (BlockBranchMap::iterator iter = Child->BranchesIn.begin(); iter != Child->BranchesIn.end(); iter++) { + Block *Parent = iter->first; + 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); + } + } + +#if 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 (CurrBlocks.find(CurrTarget) == CurrBlocks.end()) { + NextEntries.insert(CurrTarget); + Solipsize(CurrTarget, Branch::Break, Multiple, CurrBlocks); + } + iter = Next; // increment carefully because Solipsize can remove us + } + } + Multiple->InnerMap[CurrEntry] = Process(CurrBlocks, CurrEntries, NULL); + // 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 (IndependentGroups.find(Entry) == IndependentGroups.end()) { + 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"); + BlockSet *Entries = &InitialEntries; + BlockSet TempEntries[2]; + int CurrTempIndex = 0; + BlockSet *NextEntries; + Shape *Ret = NULL; + #define Make(call) \ + Shape *Temp = call; \ + if (Prev) Prev->Next = Temp; \ + if (!Ret) Ret = Temp; \ + if (!NextEntries->size()) { PrintDebug("Process() returning\n"); return Ret; } \ + Prev = Temp; \ + Entries = NextEntries; \ + continue; + while (1) { + PrintDebug("Process() running\n"); + DebugDump(Blocks, " blocks : "); + DebugDump(*Entries, " entries: "); + + CurrTempIndex = 1-CurrTempIndex; + NextEntries = &TempEntries[CurrTempIndex]; + NextEntries->clear(); + + if (Entries->size() == 0) return Ret; + if (Entries->size() == 1) { + Block *Curr = *(Entries->begin()); + if (Curr->BranchesIn.size() == 0) { + // One entry, no looping ==> Simple + Make(MakeSimple(Blocks, Curr, *NextEntries)); + } + // One entry, looping ==> Loop + Make(MakeLoop(Blocks, *Entries, *NextEntries)); + } + // More than one entry, try to eliminate through a Multiple groups of + // independent blocks from an entry/ies. It is important to remove through + // multiples as opposed to looping since the former is more performant. + BlockBlockSetMap IndependentGroups; + FindIndependentGroups(Blocks, *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 (BlockBranchMap::iterator iterBranch = Entry->BranchesIn.begin(); iterBranch != Entry->BranchesIn.end(); iterBranch++) { + Block *Origin = iterBranch->first; + if (Group.find(Origin) == Group.end()) { + // 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; + } + } + } + + 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 (int i = 0; i < Blocks.size(); i++) { + AllBlocks.insert(Blocks[i]); +#if DEBUG + PrintDebug("Adding block %d (%s)\n", Blocks[i]->Id, Blocks[i]->Code); + for (BlockBranchMap::iterator iter = Blocks[i]->BranchesOut.begin(); iter != Blocks[i]->BranchesOut.end(); iter++) { + PrintDebug(" with branch out to %d\n", iter->first->Id); + } +#endif + } + + BlockSet Entries; + Entries.insert(Entry); + Root = Analyzer(this).Process(AllBlocks, Entries, NULL); + + // Post optimizations + + struct PostOptimizer { + Relooper *Parent; + void *Closure; + + 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++) { \ + func(iter->second); \ + } + #define RECURSE_MULTIPLE(func) RECURSE_MULTIPLE_MANUAL(func, Multiple); + #define RECURSE_LOOP(func) \ + func(Loop->Inner); + + #define SHAPE_SWITCH(var, simple, multiple, loop) \ + if (SimpleShape *Simple = Shape::IsSimple(var)) { \ + simple; \ + } else if (MultipleShape *Multiple = Shape::IsMultiple(var)) { \ + multiple; \ + } else if (LoopShape *Loop = Shape::IsLoop(var)) { \ + 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); \ + } + + // 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) { + SHAPE_SWITCH(Root, { + // 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. + if (Simple->Next) { + RemoveUnneededFlows(Simple->Next, Natural); + } else { + 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 && Target->Parent == Natural) { + Details->Type = Branch::Direct; + 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(Multiple->Next, Natural); + }, { + RemoveUnneededFlows(Loop->Inner, Loop->Inner); + RemoveUnneededFlows(Loop->Next, Natural); + }); + } + + // After we know which loops exist, we can calculate which need to be labeled + void FindLabeledLoops(Shape *Root) { + bool First = Closure == NULL; + if (First) { + Closure = (void*)(new std::stack); + } + std::stack &LoopStack = *((std::stack*)Closure); + + SHAPE_SWITCH(Root, { + MultipleShape *Fused = Shape::IsMultiple(Root->Next); + // 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); + } + 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()) { + LabeledShape *Labeled = Shape::IsLabeled(Details->Ancestor); + Labeled->Labeled = true; + Details->Labeled = true; + } else { + Details->Labeled = false; + } + } + } + if (Fused && Fused->NeedLoop) { + LoopStack.pop(); + if (Fused->Next) FindLabeledLoops(Fused->Next); + } else { + if (Root->Next) FindLabeledLoops(Root->Next); + } + }, { + if (Multiple->NeedLoop) { + LoopStack.push(Multiple); + } + RECURSE_MULTIPLE(FindLabeledLoops); + if (Multiple->NeedLoop) { + LoopStack.pop(); + } + if (Root->Next) FindLabeledLoops(Root->Next); + }, { + LoopStack.push(Loop); + RECURSE_LOOP(FindLabeledLoops); + LoopStack.pop(); + if (Root->Next) FindLabeledLoops(Root->Next); + }); + + if (First) { + delete (std::stack*)Closure; + } + } + + void Process(Shape *Root) { + RemoveUnneededFlows(Root); + FindLabeledLoops(Root); + } + }; + + PrintDebug("=== Optimizing shapes ===\n"); + + PostOptimizer(this).Process(Root); +} + +void Relooper::Render() { + OutputBuffer = OutputBufferRoot; + Root->Render(false); +} + +void Relooper::SetOutputBuffer(char *Buffer, int Size) { + OutputBufferRoot = OutputBuffer = Buffer; + OutputBufferSize = Size; +} + +void Relooper::MakeOutputBuffer(int Size) { + OutputBufferRoot = OutputBuffer = (char*)malloc(Size); + OutputBufferSize = Size; +} + +#if DEBUG +// Debugging + +void DebugDump(BlockSet &Blocks, const char *prefix) { + if (prefix) printf("%s ", prefix); + for (BlockSet::iterator iter = Blocks.begin(); iter != Blocks.end(); iter++) { + printf("%d ", (*iter)->Id); + } + printf("\n"); +} + +static void PrintDebug(const char *Format, ...) { + printf("// "); + va_list Args; + va_start(Args, Format); + vprintf(Format, Args); + va_end(Args); +} +#endif + +// C API - useful for binding to other languages + +typedef std::map VoidIntMap; +VoidIntMap __blockDebugMap__; // maps block pointers in currently running code to block ids, for generated debug output + +extern "C" { + +void rl_set_output_buffer(char *buffer, int size) { +#if DEBUG + printf("#include \"Relooper.h\"\n"); + printf("int main() {\n"); + printf(" char buffer[100000];\n"); + printf(" rl_set_output_buffer(buffer);\n"); +#endif + Relooper::SetOutputBuffer(buffer, size); +} + +void rl_make_output_buffer(int size) { + Relooper::SetOutputBuffer((char*)malloc(size), size); +} + +void *rl_new_block(const char *text) { + Block *ret = new Block(text); +#if DEBUG + printf(" void *b%d = rl_new_block(\"// code %d\");\n", ret->Id, ret->Id); + __blockDebugMap__[ret] = ret->Id; + printf(" block_map[%d] = b%d;\n", ret->Id, ret->Id); +#endif + return ret; +} + +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) { +#if DEBUG + printf(" rl_block_add_branch_to(block_map[%d], block_map[%d], %s%s%s, %s%s%s);\n", ((Block*)from)->Id, ((Block*)to)->Id, condition ? "\"" : "", condition ? condition : "NULL", condition ? "\"" : "", code ? "\"" : "", code ? code : "NULL", code ? "\"" : ""); +#endif + ((Block*)from)->AddBranchTo((Block*)to, condition, code); +} + +void *rl_new_relooper() { +#if DEBUG + printf(" void *block_map[10000];\n"); + printf(" void *rl = rl_new_relooper();\n"); +#endif + return new Relooper; +} + +void rl_delete_relooper(void *relooper) { + delete (Relooper*)relooper; +} + +void rl_relooper_add_block(void *relooper, void *block) { +#if DEBUG + printf(" rl_relooper_add_block(rl, block_map[%d]);\n", ((Block*)block)->Id); +#endif + ((Relooper*)relooper)->AddBlock((Block*)block); +} + +void rl_relooper_calculate(void *relooper, void *entry) { +#if DEBUG + printf(" rl_relooper_calculate(rl, block_map[%d]);\n", ((Block*)entry)->Id); + printf(" rl_relooper_render(rl);\n"); + printf(" rl_delete_relooper(rl);\n"); + printf(" puts(buffer);\n"); + printf(" return 0;\n"); + printf("}\n"); +#endif + ((Relooper*)relooper)->Calculate((Block*)entry); +} + +void rl_relooper_render(void *relooper) { + ((Relooper*)relooper)->Render(); +} + +} + diff --git a/src/relooper/Relooper.h b/src/relooper/Relooper.h new file mode 100644 index 00000000..08ac8e40 --- /dev/null +++ b/src/relooper/Relooper.h @@ -0,0 +1,246 @@ +/* +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, and is +written in an LLVM-friendly way with the goal of inclusion in upstream +LLVM. + +[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 +#include +#include + +#ifdef __cplusplus + +#include +#include +#include + +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 + }; + 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 + bool Labeled; // If a break or continue, whether we need to use a label + const char *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 + const char *Code; // If provided, code that is run right before the branch is taken. This is useful for phis + + Branch(const char *ConditionInit, const char *CodeInit=NULL); + ~Branch(); + + // Prints out the branch + void Render(Block *Target, bool SetLabel); +}; + +typedef std::map 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; + BlockBranchMap BranchesIn; // TODO: make this just a list of Incoming, without branch info - should be just on BranchesOut + BlockBranchMap ProcessedBranchesOut; + BlockBranchMap ProcessedBranchesIn; + Shape *Parent; // The shape we are directly inside + int Id; // A unique identifier + const char *Code; // The string representation of the code in this block. Owning pointer (we copy the input) + Block *DefaultTarget; // The block we branch to without checking the condition, if none of the other conditions held. + // Since each block *must* branch somewhere, this must be set + bool IsCheckedMultipleEntry; // If true, we are a multiple entry, so reaching us requires setting the label variable + + Block(const char *CodeInit); + ~Block(); + + void AddBranchTo(Block *Target, const char *Condition, const char *Code=NULL); + + // Prints out the instructions code and branchings + void Render(bool InLoop); + + // INTERNAL + static int IdCounter; +}; + +// 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.) +// + +class SimpleShape; +class LabeledShape; +class MultipleShape; +class LoopShape; + +struct Shape { + int Id; // A unique identifier. Used to identify loops, labels are Lx where x is the Id. + Shape *Next; // The shape that will appear in the code right after this one + + enum ShapeType { + Simple, + Multiple, + Loop + }; + ShapeType Type; + + Shape(ShapeType TypeInit) : Id(Shape::IdCounter++), Next(NULL), Type(TypeInit) {} + virtual ~Shape() {} + + virtual void Render(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 LabeledShape *IsLabeled(Shape *It) { return IsMultiple(It) || IsLoop(It) ? (LabeledShape*)It : NULL; } + + // INTERNAL + static int IdCounter; +}; + +struct SimpleShape : public Shape { + Block *Inner; + + SimpleShape() : Shape(Simple), Inner(NULL) {} + void Render(bool InLoop) { + Inner->Render(InLoop); + if (Next) Next->Render(InLoop); + } +}; + +typedef std::map BlockShapeMap; + +// A shape that may be implemented with a labeled loop. +struct LabeledShape : public Shape { + bool Labeled; // If we have a loop, whether it needs to be labeled + + LabeledShape(ShapeType TypeInit) : Shape(TypeInit), Labeled(false) {} +}; + +struct MultipleShape : public LabeledShape { + BlockShapeMap InnerMap; // entry block -> shape + int NeedLoop; // If we have branches, we need a loop. This is a counter of loop requirements, + // if we optimize it to 0, the loop is unneeded + + MultipleShape() : LabeledShape(Multiple), NeedLoop(0) {} + + void RenderLoopPrefix(); + void RenderLoopPostfix(); + + void Render(bool InLoop); +}; + +struct LoopShape : public LabeledShape { + Shape *Inner; + + LoopShape() : LabeledShape(Loop), Inner(NULL) {} + void Render(bool InLoop); +}; + +/* +struct EmulatedShape : public Shape { + std::deque Blocks; + void Render(bool InLoop); +}; +*/ + +// 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 Blocks; + std::deque Shapes; + Shape *Root; + + Relooper(); + ~Relooper(); + + void AddBlock(Block *New); + + // Calculates the shapes + void Calculate(Block *Entry); + + // Renders the result. + void Render(); + + // Sets the global buffer all printing goes to. Must call this or MakeOutputBuffer. + static void SetOutputBuffer(char *Buffer, int Size); + + // Creates an output buffer. Must call this or SetOutputBuffer. + static void MakeOutputBuffer(int Size); +}; + +typedef std::set BlockSet; +typedef std::map BlockBlockSetMap; + +#if DEBUG +struct Debugging { + static void Dump(BlockSet &Blocks, const char *prefix=NULL); +}; +#endif + +#endif // __cplusplus + +// C API - useful for binding to other languages + +#ifdef _WIN32 + #ifdef RELOOPERDLL_EXPORTS + #define RELOOPERDLL_API __declspec(dllexport) + #else + #define RELOOPERDLL_API __declspec(dllimport) + #endif +#else + #define RELOOPERDLL_API +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +RELOOPERDLL_API void rl_set_output_buffer(char *buffer, int size); +RELOOPERDLL_API void rl_make_output_buffer(int size); +RELOOPERDLL_API void *rl_new_block(const char *text); +RELOOPERDLL_API void rl_delete_block(void *block); +RELOOPERDLL_API void rl_block_add_branch_to(void *from, void *to, const char *condition, const char *code); +RELOOPERDLL_API void *rl_new_relooper(); +RELOOPERDLL_API void rl_delete_relooper(void *relooper); +RELOOPERDLL_API void rl_relooper_add_block(void *relooper, void *block); +RELOOPERDLL_API void rl_relooper_calculate(void *relooper, void *entry); +RELOOPERDLL_API void rl_relooper_render(void *relooper); + +#ifdef __cplusplus +} +#endif + diff --git a/src/relooper/doit.sh b/src/relooper/doit.sh new file mode 100755 index 00000000..bf2683d5 --- /dev/null +++ b/src/relooper/doit.sh @@ -0,0 +1,68 @@ +echo "relooper" +g++ Relooper.cpp -c -g +g++ Relooper.cpp -c -g -DDEBUG -o RelooperDebug.o + +echo "test" +g++ test.cpp -c -o test.o -g +g++ Relooper.o test.o -o test + +echo "test 2" +gcc test2.c -c -o test2.o -g +g++ Relooper.o test2.o -o test2 + +echo "test 3" +gcc test3.c -c -o test3.o -g +g++ Relooper.o test3.o -o test3 + +echo "test debug" +gcc test_debug.cpp -c -o test_debug.o -g -DDEBUG +g++ RelooperDebug.o test_debug.o -o test_debug + +echo "test dead" +gcc test_dead.cpp -c -o test_dead.o -g +g++ Relooper.o test_dead.o -o test_dead + +echo "test 4" +g++ test4.cpp -c -o test4.o -g +g++ Relooper.o test4.o -o test4 + +echo "test 5" +g++ test5.cpp -c -o test5.o -g +g++ Relooper.o test5.o -o test5 + +echo "test 6" +g++ test6.cpp -c -o test6.o -g +g++ Relooper.o test6.o -o test6 + +echo "test inf" +g++ test_inf.cpp -c -o test_inf.o -g +g++ Relooper.o test_inf.o -o test_inf + +echo "test fuzz1" +g++ test_fuzz1.cpp -c -o test_fuzz1.o -g +g++ Relooper.o test_fuzz1.o -o test_fuzz1 + +echo "test fuzz2" +g++ test_fuzz2.cpp -c -o test_fuzz2.o -g +g++ Relooper.o test_fuzz2.o -o test_fuzz2 + +echo "test fuzz3" +g++ test_fuzz3.cpp -c -o test_fuzz3.o -g +g++ Relooper.o test_fuzz3.o -o test_fuzz3 + +echo "test fuzz4" +g++ test_fuzz4.cpp -c -o test_fuzz4.o -g +g++ Relooper.o test_fuzz4.o -o test_fuzz4 + +echo "test fuzz5" +g++ test_fuzz5.cpp -c -o test_fuzz5.o -g +g++ Relooper.o test_fuzz5.o -o test_fuzz5 + +echo "test fuzz6" +g++ test_fuzz6.cpp -c -o test_fuzz6.o -g +g++ Relooper.o test_fuzz6.o -o test_fuzz6 + +echo +echo "=============================" +echo + diff --git a/src/relooper/emscripten/Makefile b/src/relooper/emscripten/Makefile new file mode 100644 index 00000000..277dd538 --- /dev/null +++ b/src/relooper/emscripten/Makefile @@ -0,0 +1,18 @@ +EMSCRIPTEN = ~/Dev/emscripten +EMCC = $(EMSCRIPTEN)/emcc +BINDINGS_GENERATOR = $(EMSCRIPTEN)/tools/bindings_generator.py +NATIVIZER = $(EMSCRIPTEN)/tools/nativize_llvm.py + +all: relooper.js + +relooper.js: + $(EMCC) -O2 ../Relooper.cpp -I.. --post-js glue.js -o relooper.raw.js -s TOTAL_MEMORY=52428800 -s DEFAULT_LIBRARY_FUNCS_TO_INCLUDE='["memcpy", "memset", "malloc", "free", "puts"]' + echo "// Relooper, (C) 2012 Alon Zakai, MIT license, https://github.com/kripken/Relooper" > relooper.js + echo "var Relooper = (function() {" >> relooper.js + cat relooper.raw.js >> relooper.js + echo " return Module.Relooper;" >> relooper.js + echo "})();" >> relooper.js + +clean: + rm relooper.js + diff --git a/src/relooper/emscripten/glue.js b/src/relooper/emscripten/glue.js new file mode 100644 index 00000000..15998acf --- /dev/null +++ b/src/relooper/emscripten/glue.js @@ -0,0 +1,54 @@ + + var RBUFFER_SIZE = 20*1024*1024; + var rbuffer = _malloc(RBUFFER_SIZE); + _rl_set_output_buffer(rbuffer, RBUFFER_SIZE); + + var TBUFFER_SIZE = 10*1024*1024; + var tbuffer = _malloc(TBUFFER_SIZE); + + var RelooperGlue = {}; + RelooperGlue['init'] = function() { + this.r = _rl_new_relooper(); + }, + RelooperGlue['addBlock'] = function(text) { + assert(this.r); + assert(text.length+1 < TBUFFER_SIZE); + writeStringToMemory(text, tbuffer); + var b = _rl_new_block(tbuffer); + _rl_relooper_add_block(this.r, b); + return b; + }; + RelooperGlue['addBranch'] = function(from, to, condition, code) { + assert(this.r); + if (condition) { + assert(condition.length+1 < TBUFFER_SIZE/2); + writeStringToMemory(condition, tbuffer); + condition = tbuffer; + } else { + condition = 0; // allow undefined, null, etc. as inputs + } + if (code) { + assert(code.length+1 < TBUFFER_SIZE/2); + writeStringToMemory(code, tbuffer + TBUFFER_SIZE/2); + code = tbuffer + TBUFFER_SIZE/2; + } else { + code = 0; // allow undefined, null, etc. as inputs + } + _rl_block_add_branch_to(from, to, condition, code); + }; + RelooperGlue['render'] = function(entry) { + assert(this.r); + assert(entry); + _rl_relooper_calculate(this.r, entry); + _rl_relooper_render(this.r); + var ret = Pointer_stringify(rbuffer); + _rl_delete_relooper(this.r); + this.r = 0; + return ret; + }; + RelooperGlue['setDebug'] = function(debug) { + _rl_set_debugging(+!!debug); + }; + + Module['Relooper'] = RelooperGlue; + diff --git a/src/relooper/emscripten/test.js b/src/relooper/emscripten/test.js new file mode 100644 index 00000000..c408a912 --- /dev/null +++ b/src/relooper/emscripten/test.js @@ -0,0 +1,44 @@ +// js -m -n -e "load('relooper.js')" test.js + +function test() { + print("-- If shape --\n"); + + //Relooper.setDebug(1); + + { + Relooper.init(); + + var b_a = Relooper.addBlock("// block A\n"); + var b_b = Relooper.addBlock("// block B\n"); + var b_c = Relooper.addBlock("// block C\n"); + + Relooper.addBranch(b_a, b_b, "check == 10", "atob();"); + Relooper.addBranch(b_a, b_c, 0, "atoc();"); + + Relooper.addBranch(b_b, b_c, 0, "btoc();"); + + var output = Relooper.render(b_a); + print(output); + } + + { + Relooper.init(); + + var b_a = Relooper.addBlock("// block A\n"); + var b_b = Relooper.addBlock("// block B\n"); + var b_c = Relooper.addBlock("// block C\n"); + + Relooper.addBranch(b_a, b_b, "check == fee()"); + Relooper.addBranch(b_a, b_c, 0, 0); + + Relooper.addBranch(b_c, b_b); + + var output = Relooper.render(b_a); + print(output); + } +} + +test(); + +// TODO: wrap the relooper itself + diff --git a/src/relooper/fuzzer.py b/src/relooper/fuzzer.py new file mode 100644 index 00000000..887eab3b --- /dev/null +++ b/src/relooper/fuzzer.py @@ -0,0 +1,116 @@ + +import random, subprocess, difflib + +while True: + # Random decisions + num = random.randint(2, 250) + density = random.random() * random.random() + decisions = [random.randint(1, num*20) for x in range(num*3)] + branches = [0]*num + defaults = [0]*num + for i in range(num): + b = set([]) + bs = random.randint(1, max(1, round(density*random.random()*(num-1)))) + for j in range(bs): + b.add(random.randint(1, num-1)) + b = list(b) + defaults[i] = random.choice(b) + b.remove(defaults[i]) + branches[i] = b + print num, density + + for temp in ['fuzz', 'fuzz.fast.js', 'fuzz.slow.js', 'fuzz.cpp']: + try: + os.unlink(temp) + except: + pass + + # parts + entry = '''print('entry'); var label; var state; var decisions = %s; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] }''' % str(decisions) + + slow = entry + '\n' + for i in range(len(branches[0])): + if i > 0: slow += 'else ' + b = branches[0] + slow += 'if (state %% %d == %d) { label = %d; }\n' % (len(b)+1, i, b[i]) # TODO: split range 1-n into these options + if len(branches[0]): slow += 'else ' + slow += 'label = %d;\n' % defaults[0] + + slow += ''' +while(1) switch(label) { +''' + + fast = ''' + +#include +#include "Relooper.h" + +int main() { + char *buffer = (char*)malloc(10*1024*1024); + Relooper::SetOutputBuffer(buffer, 10*1024*1024); +''' + + for i in range(1, num): + slow += ' case %d: print(%d); state = check(); \n' % (i, i) + b = branches[i] + for j in range(len(b)): + slow += ' if (state %% %d == %d) { label = %d; break }\n' % (len(b)+1, j, b[j]) # TODO: split range 1-n into these options + slow += ' label = %d; break\n' % defaults[i] + + for i in range(num): + if i == 0: + fast += ''' + Block *b%d = new Block("%s"); +''' % (i, entry) + else: + fast += ''' Block *b%d = new Block("print(%d); state = check();%s"); +''' % (i, i, '// ' + ('.' * int(random.expovariate(0.5/num)))) + + for i in range(num): + b = branches[i] + for j in range(len(b)): + fast += ''' b%d->AddBranchTo(b%d, "state %% %d == %d"); +''' % (i, b[j], len(b)+1, j) + fast += ''' b%d->AddBranchTo(b%d, NULL); +''' % (i, defaults[i]) + + fast += ''' + Relooper r; +''' + + for i in range(num): + fast += ''' r.AddBlock(b%d); +''' % i + + fast += ''' + r.Calculate(b0); + printf("\\n\\n"); + r.Render(); + + puts(buffer); + + return 1; +} +''' + + slow += '}' + + open('fuzz.slow.js', 'w').write(slow) + open('fuzz.cpp', 'w').write(fast) + print '_' + slow_out = subprocess.Popen(['/home/alon/Dev/mozilla-central/js/src/fast/js', '-m', '-n', 'fuzz.slow.js'], stdout=subprocess.PIPE).communicate()[0] + + print '.' + subprocess.call(['g++', 'fuzz.cpp', 'Relooper.o', '-o', 'fuzz', '-g']) + print '*' + subprocess.call(['./fuzz'], stdout=open('fuzz.fast.js', 'w')) + print '-' + fast_out = subprocess.Popen(['/home/alon/Dev/mozilla-central/js/src/fast/js', '-m', '-n', 'fuzz.fast.js'], stdout=subprocess.PIPE).communicate()[0] + print + + if slow_out != fast_out: + print ''.join([a.rstrip()+'\n' for a in difflib.unified_diff(slow_out.split('\n'), fast_out.split('\n'), fromfile='slow', tofile='fast')]) + assert False + + #break + diff --git a/src/relooper/ministring.h b/src/relooper/ministring.h new file mode 100644 index 00000000..d0f042c8 --- /dev/null +++ b/src/relooper/ministring.h @@ -0,0 +1,35 @@ + +// Tiny implementation of strings. Avoids linking in all of std::string + +#include +#include + +class ministring { + int used; + char *buffer; + int bufferSize; +public: + ministring() : used(0), buffer(NULL), bufferSize(0) {} + ~ministring() { if (buffer) free(buffer); } + + char *c_str() { return buffer; } + int size() { return used; } + + void clear() { + used = 0; // keep the buffer alive as an optimization, just resize + } + + ministring& operator+=(const char *s) { + int len = strlen(s); + if (used + len + 2 > bufferSize) { + // try to avoid frequent reallocations + bufferSize = 2*(bufferSize + len); + bufferSize += 1024 - bufferSize % 1024; + buffer = (char*)(buffer ? realloc(buffer, bufferSize) : malloc(bufferSize)); + } + strcpy(buffer + used, s); + used += len; + return *this; + } +}; + diff --git a/src/relooper/paper.pdf b/src/relooper/paper.pdf new file mode 100644 index 00000000..401162ac Binary files /dev/null and b/src/relooper/paper.pdf differ diff --git a/src/relooper/test.cpp b/src/relooper/test.cpp new file mode 100644 index 00000000..0d029216 --- /dev/null +++ b/src/relooper/test.cpp @@ -0,0 +1,195 @@ + +#include "Relooper.h" + +int main() { + char buffer[10000]; + + if (1) { + Relooper::SetOutputBuffer(buffer, sizeof(buffer)); + + printf("\n\n-- If pattern --\n\n"); + + Block *b_a = new Block("// block A\n"); + Block *b_b = new Block("// block B\n"); + Block *b_c = new Block("// block C\n"); + + b_a->AddBranchTo(b_b, "check == 10", "atob();"); + b_a->AddBranchTo(b_c, NULL, "atoc();"); + + b_b->AddBranchTo(b_c, NULL, "btoc();"); + + Relooper r; + r.AddBlock(b_a); + r.AddBlock(b_b); + r.AddBlock(b_c); + + r.Calculate(b_a); + printf("\n\n"); + r.Render(); + + puts(buffer); + } + + if (1) { + Relooper::SetOutputBuffer(buffer, sizeof(buffer)); + + printf("\n\n-- If-else pattern --\n\n"); + + Block *b_a = new Block("// block A\n"); + Block *b_b = new Block("// block B\n"); + Block *b_c = new Block("// block C\n"); + Block *b_d = new Block("// block D\n"); + + b_a->AddBranchTo(b_b, "check == 15"); + b_a->AddBranchTo(b_c, NULL); + + b_b->AddBranchTo(b_d, NULL); + + b_c->AddBranchTo(b_d, NULL); + + Relooper r; + r.AddBlock(b_a); + r.AddBlock(b_b); + r.AddBlock(b_c); + r.AddBlock(b_d); + + r.Calculate(b_a); + printf("\n\n"); + r.Render(); + + puts(buffer); + } + + if (1) { + Relooper::SetOutputBuffer(buffer, sizeof(buffer)); + + printf("\n\n-- Loop + tail pattern --\n\n"); + + Block *b_a = new Block("// block A\nvar check = maybe();\n"); + Block *b_b = new Block("// block B\n"); + Block *b_c = new Block("// block C\n"); + + b_a->AddBranchTo(b_b, NULL); + + b_b->AddBranchTo(b_a, "check == 41"); + b_b->AddBranchTo(b_c, NULL); + + Relooper r; + r.AddBlock(b_a); + r.AddBlock(b_b); + r.AddBlock(b_c); + + r.Calculate(b_a); + printf("\n\n"); + r.Render(); + + puts(buffer); + } + + if (1) { + Relooper::SetOutputBuffer(buffer, sizeof(buffer)); + + printf("\n\n-- Loop with phi to head \n\n"); + + void *block_map[10000]; + void *rl = rl_new_relooper(); + void *b1 = rl_new_block("// code 1"); + block_map[1] = b1; + rl_relooper_add_block(rl, block_map[1]); + void *b2 = rl_new_block("// code 2"); + block_map[2] = b2; + rl_relooper_add_block(rl, block_map[2]); + void *b3 = rl_new_block("// code 3"); + block_map[3] = b3; + rl_relooper_add_block(rl, block_map[3]); + void *b4 = rl_new_block("// code 4"); + block_map[4] = b4; + rl_relooper_add_block(rl, block_map[4]); + void *b5 = rl_new_block("// code 5"); + block_map[5] = b5; + rl_relooper_add_block(rl, block_map[5]); + void *b6 = rl_new_block("// code 6"); + block_map[6] = b6; + rl_relooper_add_block(rl, block_map[6]); + void *b7 = rl_new_block("// code 7"); + block_map[7] = b7; + rl_relooper_add_block(rl, block_map[7]); + rl_block_add_branch_to(block_map[1], block_map[2], NULL, "var $i_0 = 0;var $x_0 = 5; "); + rl_block_add_branch_to(block_map[2], block_map[3], "$2", NULL); + rl_block_add_branch_to(block_map[2], block_map[7], NULL, "var $x_1 = $x_0; "); + rl_block_add_branch_to(block_map[3], block_map[4], "$6", NULL); + rl_block_add_branch_to(block_map[3], block_map[2], NULL, "var $i_0 = $7;var $x_0 = $5; "); + rl_block_add_branch_to(block_map[4], block_map[5], "$10", NULL); + rl_block_add_branch_to(block_map[4], block_map[6], NULL, NULL); + rl_block_add_branch_to(block_map[5], block_map[6], NULL, NULL); + rl_block_add_branch_to(block_map[6], block_map[7], NULL, "var $x_1 = $13; "); + rl_relooper_calculate(rl, block_map[1]); + rl_relooper_render(rl); + rl_delete_relooper(rl); + puts(buffer); + } + + if (1) { + Relooper::SetOutputBuffer(buffer, sizeof(buffer)); + + printf("\n\n-- phi on split dead ends --\n\n"); + + Block *b_a = new Block("// block A...................................................................................................\n"); + Block *b_b = new Block("// block B...................................................................................................\n"); + Block *b_c = new Block("// block C...................................................................................................\n"); + Block *b_d = new Block("// block D\n"); // small and splittable! + Block *b_e = new Block("// block E\n"); + + b_a->AddBranchTo(b_b, "chak()", "atob();"); + b_a->AddBranchTo(b_c, NULL, "atoc();"); + + b_b->AddBranchTo(b_d, NULL, "btod();"); + + b_c->AddBranchTo(b_d, NULL, "ctod2();"); + + Relooper r; + r.AddBlock(b_a); + r.AddBlock(b_b); + r.AddBlock(b_c); + r.AddBlock(b_d); + r.AddBlock(b_e); + + r.Calculate(b_a); + printf("\n\n"); + r.Render(); + + puts(buffer); + } +/* + if (1) { + Relooper::SetOutputBuffer(buffer, sizeof(buffer)); + + printf("\n\n-- Unbalanced with a dead end --\n\n"); + + Block *b_a = new Block("// block A\n"); + Block *b_b = new Block("// block B\n"); + Block *b_c = new Block("// block C\n"); + Block *b_d = new Block("// block D\n"); + + b_a->AddBranchTo(b_b, "check == 10"); + b_a->AddBranchTo(b_c, NULL); + + b_b->AddBranchTo(b_d, NULL); + + b_d->AddBranchTo(b_b, NULL); + + Relooper r; + r.AddBlock(b_a); + r.AddBlock(b_b); + r.AddBlock(b_c); + r.AddBlock(b_d); + + r.Calculate(b_a); + printf("\n\n"); + r.Render(); + + puts(buffer); + } +*/ +} + diff --git a/src/relooper/test.txt b/src/relooper/test.txt new file mode 100644 index 00000000..ff4ada24 --- /dev/null +++ b/src/relooper/test.txt @@ -0,0 +1,99 @@ + + +-- If pattern -- + + + +// block A +if (check == 10) { + atob(); + // block B + btoc(); +} else { + atoc(); +} +// block C + + + +-- If-else pattern -- + + + +// block A +if (check == 15) { + // block B +} else { + // block C +} +// block D + + + +-- Loop + tail pattern -- + + + +while(1) { + // block A + var check = maybe(); + // block B + if (!(check == 41)) { + break; + } +} +// block C + + + +-- Loop with phi to head + +// code 1 +var $i_0 = 0;var $x_0 = 5; +while(1) { + // code 2 + if (!($2)) { + var $x_1 = $x_0; + label = 18; + break; + } + // code 3 + if ($6) { + label = 14; + break; + } else { + var $i_0 = $7;var $x_0 = $5; + } +} +if (label == 14) { + // code 4 + if ($10) { + // code 5 + } + // code 6 + var $x_1 = $13; + // code 7 +} +else if (label == 18) { + // code 7 +} + + + +-- phi on split dead ends -- + + + +// block A................................................................................................... +if (chak()) { + atob(); + // block B................................................................................................... + btod(); + // block D +} else { + atoc(); + // block C................................................................................................... + ctod2(); + // block D +} + diff --git a/src/relooper/test2.c b/src/relooper/test2.c new file mode 100644 index 00000000..118a2627 --- /dev/null +++ b/src/relooper/test2.c @@ -0,0 +1,44 @@ + +#include "Relooper.h" + +int main() { + char buffer[10000]; + rl_set_output_buffer(buffer, sizeof(buffer)); + + void *r = rl_new_relooper(); + void *ep = rl_new_block("ep"); + rl_relooper_add_block(r, ep); + void *LBB1 = rl_new_block("LBB1"); + rl_relooper_add_block(r, LBB1); + void *LBB2 = rl_new_block("LBB2"); + rl_relooper_add_block(r, LBB2); + void *LBB3 = rl_new_block("LBB3"); + rl_relooper_add_block(r, LBB3); +/* + void *LBB4 = rl_new_block("LBB4"); + rl_relooper_add_block(r, LBB4); + void *LBB5 = rl_new_block("LBB5"); + rl_relooper_add_block(r, LBB5); + void *LBB6 = rl_new_block("LBB6"); + rl_relooper_add_block(r, LBB6); +*/ + rl_block_add_branch_to(ep, LBB1, "ep -> LBB1", NULL); + rl_block_add_branch_to(ep, LBB3, NULL, NULL); + rl_block_add_branch_to(LBB1, LBB2, "LBB1 -> LBB2", NULL); + rl_block_add_branch_to(LBB1, LBB3, NULL, NULL); + rl_block_add_branch_to(LBB2, LBB3, NULL, NULL); +// rl_block_add_branch_to(LBB3, LBB4, "LBB3 -> LBB4"); +// rl_block_add_branch_to(LBB3, LBB6, "LBB3 -> LBB6"); +/* + rl_block_add_branch_to(LBB4, LBB5, "LBB4 -> LBB5"); + rl_block_add_branch_to(LBB4, LBB6, "LBB4 -> LBB6"); + rl_block_add_branch_to(LBB5, LBB6, "LBB5 -> LBB6"); + rl_block_add_branch_to(LBB5, LBB5, "LBB5 -> LBB5"); +*/ + rl_relooper_calculate(r, ep); + rl_relooper_render(r); + rl_delete_relooper(r); + + puts(buffer); +} + diff --git a/src/relooper/test2.txt b/src/relooper/test2.txt new file mode 100644 index 00000000..c77ce491 --- /dev/null +++ b/src/relooper/test2.txt @@ -0,0 +1,12 @@ +ep +do { + if (ep -> LBB1) { + LBB1 + if (!(LBB1 -> LBB2)) { + break; + } + LBB2 + } +} while(0); +LBB3 + diff --git a/src/relooper/test3.c b/src/relooper/test3.c new file mode 100644 index 00000000..2cef14fb --- /dev/null +++ b/src/relooper/test3.c @@ -0,0 +1,42 @@ + +#include "Relooper.h" + +int main() { + char buffer[10000]; + rl_set_output_buffer(buffer, sizeof(buffer)); + + void *r = rl_new_relooper(); + void *ep = rl_new_block("ep"); + rl_relooper_add_block(r, ep); + void *LBB1 = rl_new_block("LBB1"); + rl_relooper_add_block(r, LBB1); + void *LBB2 = rl_new_block("LBB2"); + rl_relooper_add_block(r, LBB2); + void *LBB3 = rl_new_block("LBB3"); + rl_relooper_add_block(r, LBB3); + void *LBB4 = rl_new_block("LBB4"); + rl_relooper_add_block(r, LBB4); + void *LBB5 = rl_new_block("LBB5"); + rl_relooper_add_block(r, LBB5); + void *LBB6 = rl_new_block("LBB6"); + rl_relooper_add_block(r, LBB6); + + rl_block_add_branch_to(ep, LBB1, "ep -> LBB1", NULL); + rl_block_add_branch_to(ep, LBB3, NULL, NULL); + rl_block_add_branch_to(LBB1, LBB2, "LBB1 -> LBB2", NULL); + rl_block_add_branch_to(LBB1, LBB3, NULL, NULL); + rl_block_add_branch_to(LBB2, LBB3, NULL, NULL); + rl_block_add_branch_to(LBB3, LBB4, "LBB3 -> LBB4", NULL); + rl_block_add_branch_to(LBB3, LBB6, NULL, NULL); + rl_block_add_branch_to(LBB4, LBB5, "LBB4 -> LBB5", NULL); + rl_block_add_branch_to(LBB4, LBB6, NULL, NULL); + rl_block_add_branch_to(LBB5, LBB6, "LBB5 -> LBB6", NULL); + rl_block_add_branch_to(LBB5, LBB5, NULL, NULL); + + rl_relooper_calculate(r, ep); + rl_relooper_render(r); + rl_delete_relooper(r); + + puts(buffer); +} + diff --git a/src/relooper/test3.txt b/src/relooper/test3.txt new file mode 100644 index 00000000..696542ef --- /dev/null +++ b/src/relooper/test3.txt @@ -0,0 +1,27 @@ +ep +do { + if (ep -> LBB1) { + LBB1 + if (!(LBB1 -> LBB2)) { + break; + } + LBB2 + } +} while(0); +LBB3 +L5: do { + if (LBB3 -> LBB4) { + LBB4 + if (!(LBB4 -> LBB5)) { + break; + } + while(1) { + LBB5 + if (LBB5 -> LBB6) { + break L5; + } + } + } +} while(0); +LBB6 + diff --git a/src/relooper/test4.cpp b/src/relooper/test4.cpp new file mode 100644 index 00000000..76fc8ec0 --- /dev/null +++ b/src/relooper/test4.cpp @@ -0,0 +1,40 @@ + +#include "Relooper.h" + +int main() { + char buffer[10000]; + rl_set_output_buffer(buffer, sizeof(buffer)); + + void *r = rl_new_relooper(); + + void *b19 = rl_new_block("//19"); + rl_relooper_add_block(r, b19); + void *b20 = rl_new_block("//20"); + rl_relooper_add_block(r, b20); + void *b21 = rl_new_block("//21"); + rl_relooper_add_block(r, b21); + void *b22 = rl_new_block("//22"); + rl_relooper_add_block(r, b22); + void *b23 = rl_new_block("//23"); + rl_relooper_add_block(r, b23); + void *b24 = rl_new_block("//24"); + rl_relooper_add_block(r, b24); + void *b28 = rl_new_block("//28"); + rl_relooper_add_block(r, b28); + + rl_block_add_branch_to(b19, b20, " 1 ", NULL); + rl_block_add_branch_to(b19, b22, NULL, NULL); + rl_block_add_branch_to(b20, b21, " 1 ", NULL); + rl_block_add_branch_to(b20, b22, NULL, NULL); + rl_block_add_branch_to(b21, b23, NULL, NULL); + rl_block_add_branch_to(b22, b23, NULL, NULL); + rl_block_add_branch_to(b23, b24, " 1 ", NULL); + rl_block_add_branch_to(b23, b28, NULL, NULL); + + rl_relooper_calculate(r, b19); + rl_relooper_render(r); + rl_delete_relooper(r); + + puts(buffer); +} + diff --git a/src/relooper/test4.txt b/src/relooper/test4.txt new file mode 100644 index 00000000..f0bfb972 --- /dev/null +++ b/src/relooper/test4.txt @@ -0,0 +1,24 @@ +//19 +do { + if ( 1 ) { + //20 + if (!( 1 )) { + label = 4; + break; + } + //21 + break; + } else { + label = 4; + } +} while(0); +if (label == 4) { + //22 +} +//23 +if ( 1 ) { + //24 +} else { + //28 +} + diff --git a/src/relooper/test5.cpp b/src/relooper/test5.cpp new file mode 100644 index 00000000..f86da2b3 --- /dev/null +++ b/src/relooper/test5.cpp @@ -0,0 +1,40 @@ + +#include "Relooper.h" + +int main() { + char buffer[10000]; + rl_set_output_buffer(buffer, sizeof(buffer)); + + void *r = rl_new_relooper(); + + void *b0 = rl_new_block("//0"); + rl_relooper_add_block(r, b0); + void *b1 = rl_new_block("//1"); + rl_relooper_add_block(r, b1); + void *b2 = rl_new_block("//2"); + rl_relooper_add_block(r, b2); + void *b3 = rl_new_block("//3"); + rl_relooper_add_block(r, b3); + void *b4 = rl_new_block("//4"); + rl_relooper_add_block(r, b4); + void *b5 = rl_new_block("//5"); + rl_relooper_add_block(r, b5); + + rl_block_add_branch_to(b0, b1, "check(0)", NULL); + rl_block_add_branch_to(b0, b4, NULL, "goingFrom0to4();"); + rl_block_add_branch_to(b1, b1, "check(1)", NULL); + rl_block_add_branch_to(b1, b2, NULL, NULL); + rl_block_add_branch_to(b2, b2, "check(2)", NULL); + rl_block_add_branch_to(b2, b3, NULL, NULL); + rl_block_add_branch_to(b4, b4, "check(4)", NULL); + rl_block_add_branch_to(b4, b5, NULL, NULL); + rl_block_add_branch_to(b5, b3, "check(5)", NULL); + rl_block_add_branch_to(b5, b5, NULL, NULL); + + rl_relooper_calculate(r, b0); + rl_relooper_render(r); + rl_delete_relooper(r); + + puts(buffer); +} + diff --git a/src/relooper/test5.txt b/src/relooper/test5.txt new file mode 100644 index 00000000..ad769ae7 --- /dev/null +++ b/src/relooper/test5.txt @@ -0,0 +1,32 @@ +//0 +if (check(0)) { + while(1) { + //1 + if (!(check(1))) { + break; + } + } + while(1) { + //2 + if (!(check(2))) { + break; + } + } + //3 +} else { + goingFrom0to4(); + while(1) { + //4 + if (!(check(4))) { + break; + } + } + while(1) { + //5 + if (check(5)) { + break; + } + } + //3 +} + diff --git a/src/relooper/test6.cpp b/src/relooper/test6.cpp new file mode 100644 index 00000000..90453d4c --- /dev/null +++ b/src/relooper/test6.cpp @@ -0,0 +1,31 @@ + +#include "Relooper.h" + +int main() { + char buffer[10000]; + rl_set_output_buffer(buffer, sizeof(buffer)); + + void *r = rl_new_relooper(); + + void *b0 = rl_new_block("//0"); + rl_relooper_add_block(r, b0); + void *b1 = rl_new_block("//1"); + rl_relooper_add_block(r, b1); + void *b2 = rl_new_block("//2"); + rl_relooper_add_block(r, b2); + void *b3 = rl_new_block("//3"); + rl_relooper_add_block(r, b3); + + rl_block_add_branch_to(b0, b1, "check(0)", NULL); + rl_block_add_branch_to(b0, b3, NULL, NULL); + rl_block_add_branch_to(b1, b2, "check(1)", NULL); + rl_block_add_branch_to(b1, b3, NULL, NULL); + rl_block_add_branch_to(b2, b3, NULL, NULL); + + rl_relooper_calculate(r, b0); + rl_relooper_render(r); + rl_delete_relooper(r); + + puts(buffer); +} + diff --git a/src/relooper/test6.txt b/src/relooper/test6.txt new file mode 100644 index 00000000..c5effd08 --- /dev/null +++ b/src/relooper/test6.txt @@ -0,0 +1,12 @@ +//0 +do { + if (check(0)) { + //1 + if (!(check(1))) { + break; + } + //2 + } +} while(0); +//3 + diff --git a/src/relooper/test_dead.cpp b/src/relooper/test_dead.cpp new file mode 100644 index 00000000..887d254c --- /dev/null +++ b/src/relooper/test_dead.cpp @@ -0,0 +1,28 @@ + +#include "Relooper.h" + +int main() { + char buffer[10000]; + + Relooper::SetOutputBuffer(buffer, sizeof(buffer)); + + printf("\n\n-- If pattern --\n\n"); + + Block *b_a = new Block("// block A\n"); + Block *b_b = new Block("// block B\n"); // never reached + + b_b->AddBranchTo(b_b, NULL); + + Relooper r; + r.AddBlock(b_a); + r.AddBlock(b_b); + + r.Calculate(b_a); + printf("\n\n"); + r.Render(); + + puts(buffer); + + printf("I did not crash even though I have dead code with a branch!\n"); +} + diff --git a/src/relooper/test_dead.txt b/src/relooper/test_dead.txt new file mode 100644 index 00000000..ae54e2cd --- /dev/null +++ b/src/relooper/test_dead.txt @@ -0,0 +1,9 @@ + + +-- If pattern -- + + + +// block A + +I did not crash even though I have dead code with a branch! diff --git a/src/relooper/test_debug.cpp b/src/relooper/test_debug.cpp new file mode 100644 index 00000000..14511b62 --- /dev/null +++ b/src/relooper/test_debug.cpp @@ -0,0 +1,30 @@ + +#include "Relooper.h" + +int main() { + char buffer[10000]; + rl_set_output_buffer(buffer, sizeof(buffer)); + + void *r = rl_new_relooper(); + void *ep = rl_new_block("ep"); + rl_relooper_add_block(r, ep); + void *LBB1 = rl_new_block("LBB1"); + rl_relooper_add_block(r, LBB1); + void *LBB2 = rl_new_block("LBB2"); + rl_relooper_add_block(r, LBB2); + void *LBB3 = rl_new_block("LBB3"); + rl_relooper_add_block(r, LBB3); + + rl_block_add_branch_to(ep, LBB1, "ep -> LBB1", NULL); + rl_block_add_branch_to(ep, LBB3, NULL, NULL); + rl_block_add_branch_to(LBB1, LBB2, "LBB1 -> LBB2", NULL); + rl_block_add_branch_to(LBB1, LBB3, NULL, NULL); + rl_block_add_branch_to(LBB2, LBB3, NULL, NULL); + + rl_relooper_calculate(r, ep); + rl_relooper_render(r); + rl_delete_relooper(r); + + puts(buffer); +} + diff --git a/src/relooper/test_debug.txt b/src/relooper/test_debug.txt new file mode 100644 index 00000000..1c7d0508 --- /dev/null +++ b/src/relooper/test_debug.txt @@ -0,0 +1,96 @@ +#include "Relooper.h" +int main() { + char buffer[100000]; + rl_set_output_buffer(buffer); + void *block_map[10000]; + void *rl = rl_new_relooper(); + void *b1 = rl_new_block("// code 1"); + block_map[1] = b1; + rl_relooper_add_block(rl, block_map[1]); + void *b2 = rl_new_block("// code 2"); + block_map[2] = b2; + rl_relooper_add_block(rl, block_map[2]); + void *b3 = rl_new_block("// code 3"); + block_map[3] = b3; + rl_relooper_add_block(rl, block_map[3]); + void *b4 = rl_new_block("// code 4"); + block_map[4] = b4; + rl_relooper_add_block(rl, block_map[4]); + rl_block_add_branch_to(block_map[1], block_map[2], "ep -> LBB1", NULL); + rl_block_add_branch_to(block_map[1], block_map[4], NULL, NULL); + rl_block_add_branch_to(block_map[2], block_map[3], "LBB1 -> LBB2", NULL); + rl_block_add_branch_to(block_map[2], block_map[4], NULL, NULL); + rl_block_add_branch_to(block_map[3], block_map[4], NULL, NULL); + rl_relooper_calculate(rl, block_map[1]); + rl_relooper_render(rl); + rl_delete_relooper(rl); + puts(buffer); + return 0; +} +// Adding block 1 (ep) +// with branch out to 2 +// with branch out to 4 +// Adding block 2 (LBB1) +// with branch out to 3 +// with branch out to 4 +// Adding block 3 (LBB2) +// with branch out to 4 +// Adding block 4 (LBB3) +// Process() called +// Process() running + blocks : 1 2 3 4 + entries: 1 +// creating simple block with block #1 +// Solipsizing branches into 2 + relevant to solipsize: 1 +// eliminated branch from 1 +// Solipsizing branches into 4 + relevant to solipsize: 1 +// eliminated branch from 1 +// Process() running + blocks : 2 3 4 + entries: 2 4 +// Investigated independent groups: + group: 2 3 +// Independent groups: 1 +// Handleable independent groups: 1 +// creating multiple block with 1 inner groups +// multiple group with entry 2: + 2 3 +// Solipsizing branches into 4 + relevant to solipsize: 2 3 +// eliminated branch from 2 +// eliminated branch from 3 +// Process() called +// Process() running + blocks : 2 3 + entries: 2 +// creating simple block with block #2 +// Solipsizing branches into 3 + relevant to solipsize: 2 +// eliminated branch from 2 +// Process() running + blocks : 3 + entries: 3 +// creating simple block with block #3 +// Process() returning + remaining blocks after multiple: 4 +// Process() running + blocks : 4 + entries: 4 +// creating simple block with block #4 +// Process() returning +// === Optimizing shapes === +// Fusing Multiple to Simple +ep +do { + if (ep -> LBB1) { + LBB1 + if (!(LBB1 -> LBB2)) { + break; + } + LBB2 + } +} while(0); +LBB3 + diff --git a/src/relooper/test_fuzz1.cpp b/src/relooper/test_fuzz1.cpp new file mode 100644 index 00000000..54205694 --- /dev/null +++ b/src/relooper/test_fuzz1.cpp @@ -0,0 +1,52 @@ + + +#include +#include "Relooper.h" + +int main() { + #define SIZE (10*1024*1024) + char *buffer = (char*)malloc(SIZE); + Relooper::SetOutputBuffer(buffer, SIZE); + + Block *b0 = new Block("print('entry'); var label; var state; var decisions = [4, 1, 7, 2, 6, 6, 8]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] }"); + Block *b1 = new Block("print(1); state = check();"); + Block *b2 = new Block("print(2); state = check();"); + Block *b3 = new Block("print(3); state = check();"); + Block *b4 = new Block("print(4); state = check();"); + Block *b5 = new Block("print(5); state = check();"); + Block *b6 = new Block("print(6); state = check();"); + Block *b7 = new Block("print(7); state = check();"); + Block *b8 = new Block("print(8); state = check();"); + b0->AddBranchTo(b5, NULL); + b1->AddBranchTo(b3, NULL); + b2->AddBranchTo(b1, NULL); + b3->AddBranchTo(b8, "state == 8"); + b3->AddBranchTo(b1, NULL); + b4->AddBranchTo(b3, "state == 3"); + b4->AddBranchTo(b1, NULL); + b5->AddBranchTo(b6, NULL); + b6->AddBranchTo(b7, "state == 7"); + b6->AddBranchTo(b1, NULL); + b7->AddBranchTo(b2, NULL); + b8->AddBranchTo(b4, "state == 4"); + b8->AddBranchTo(b2, NULL); + + Relooper r; + r.AddBlock(b0); + r.AddBlock(b1); + r.AddBlock(b2); + r.AddBlock(b3); + r.AddBlock(b4); + r.AddBlock(b5); + r.AddBlock(b6); + r.AddBlock(b7); + r.AddBlock(b8); + + r.Calculate(b0); + printf("\n\n"); + r.Render(); + + puts(buffer); + + return 1; +} diff --git a/src/relooper/test_fuzz1.txt b/src/relooper/test_fuzz1.txt new file mode 100644 index 00000000..63bbee0c --- /dev/null +++ b/src/relooper/test_fuzz1.txt @@ -0,0 +1,44 @@ + + +print('entry'); var label; var state; var decisions = [4, 1, 7, 2, 6, 6, 8]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] } +print(5); state = check(); +print(6); state = check(); +do { + if (state == 7) { + print(7); state = check(); + label = 3; + break; + } else { + label = 2; + } +} while(0); +L5: while(1) { + if (label == 2) { + label = 0; + print(1); state = check(); + while(1) { + print(3); state = check(); + if (!(state == 8)) { + label = 2; + continue L5; + } + print(8); state = check(); + if (!(state == 4)) { + label = 3; + continue L5; + } + print(4); state = check(); + if (!(state == 3)) { + label = 2; + continue L5; + } + } + } + else if (label == 3) { + label = 0; + print(2); state = check(); + label = 2; + continue; + } +} + diff --git a/src/relooper/test_fuzz2.cpp b/src/relooper/test_fuzz2.cpp new file mode 100644 index 00000000..00375340 --- /dev/null +++ b/src/relooper/test_fuzz2.cpp @@ -0,0 +1,34 @@ + + +#include +#include "Relooper.h" + +int main() { + #define SIZE (10*1024*1024) + char *buffer = (char*)malloc(SIZE); + Relooper::SetOutputBuffer(buffer, SIZE); + + Block *b0 = new Block("print('entry'); var label; var state; var decisions = [4, 1, 4, 3, 4, 1, 2, 5, 1, 3, 5, 5, 1, 5, 2, 4, 4, 3]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] }"); + Block *b1 = new Block("print(1); state = check();"); + Block *b2 = new Block("print(2); state = check();"); + Block *b3 = new Block("print(3); state = check();"); + b0->AddBranchTo(b1, "state == 1"); + b0->AddBranchTo(b3, NULL); + b1->AddBranchTo(b1, NULL); + b2->AddBranchTo(b3, NULL); + b3->AddBranchTo(b2, NULL); + + Relooper r; + r.AddBlock(b0); + r.AddBlock(b1); + r.AddBlock(b2); + r.AddBlock(b3); + + r.Calculate(b0); + printf("\n\n"); + r.Render(); + + puts(buffer); + + return 1; +} diff --git a/src/relooper/test_fuzz2.txt b/src/relooper/test_fuzz2.txt new file mode 100644 index 00000000..c48c6b6c --- /dev/null +++ b/src/relooper/test_fuzz2.txt @@ -0,0 +1,14 @@ + + +print('entry'); var label; var state; var decisions = [4, 1, 4, 3, 4, 1, 2, 5, 1, 3, 5, 5, 1, 5, 2, 4, 4, 3]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] } +if (state == 1) { + while(1) { + print(1); state = check(); + } +} else { + while(1) { + print(3); state = check(); + print(2); state = check(); + } +} + diff --git a/src/relooper/test_fuzz3.cpp b/src/relooper/test_fuzz3.cpp new file mode 100644 index 00000000..3f39f5da --- /dev/null +++ b/src/relooper/test_fuzz3.cpp @@ -0,0 +1,36 @@ + + +#include +#include "Relooper.h" + +int main() { + #define SIZE (10*1024*1024) + char *buffer = (char*)malloc(SIZE); + Relooper::SetOutputBuffer(buffer, SIZE); + + Block *b0 = new Block("print('entry'); var label; var state; var decisions = [3, 3, 4, 1, 2, 1, 2, 4, 4, 4, 2, 3, 3, 1, 2]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] }"); + Block *b1 = new Block("print(1); state = check();"); + Block *b2 = new Block("print(2); state = check();"); + Block *b3 = new Block("print(3); state = check();"); + Block *b4 = new Block("print(4); state = check();"); + b0->AddBranchTo(b1, NULL); + b1->AddBranchTo(b3, NULL); + b2->AddBranchTo(b1, NULL); + b3->AddBranchTo(b4, NULL); + b4->AddBranchTo(b4, NULL); + + Relooper r; + r.AddBlock(b0); + r.AddBlock(b1); + r.AddBlock(b2); + r.AddBlock(b3); + r.AddBlock(b4); + + r.Calculate(b0); + printf("\n\n"); + r.Render(); + + puts(buffer); + + return 1; +} diff --git a/src/relooper/test_fuzz3.txt b/src/relooper/test_fuzz3.txt new file mode 100644 index 00000000..aeeccf87 --- /dev/null +++ b/src/relooper/test_fuzz3.txt @@ -0,0 +1,9 @@ + + +print('entry'); var label; var state; var decisions = [3, 3, 4, 1, 2, 1, 2, 4, 4, 4, 2, 3, 3, 1, 2]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] } +print(1); state = check(); +print(3); state = check(); +while(1) { + print(4); state = check(); +} + diff --git a/src/relooper/test_fuzz4.cpp b/src/relooper/test_fuzz4.cpp new file mode 100644 index 00000000..8f969386 --- /dev/null +++ b/src/relooper/test_fuzz4.cpp @@ -0,0 +1,38 @@ + + +#include +#include "Relooper.h" + +int main() { + #define SIZE (10*1024*1024) + char *buffer = (char*)malloc(SIZE); + Relooper::SetOutputBuffer(buffer, SIZE); + + Block *b0 = new Block("print('entry'); var label; var state; var decisions = [2, 2, 1, 3, 2, 2, 1, 3, 2, 3, 3, 1, 3, 2, 1]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] }"); + Block *b1 = new Block("print(1); state = check();"); + Block *b2 = new Block("print(2); state = check();"); + Block *b3 = new Block("print(3); state = check();"); + Block *b4 = new Block("print(4); state = check();"); + b0->AddBranchTo(b2, "state == 2"); + b0->AddBranchTo(b4, NULL); + b1->AddBranchTo(b1, NULL); + b2->AddBranchTo(b2, NULL); + b3->AddBranchTo(b1, NULL); + b4->AddBranchTo(b4, "state == 4"); + b4->AddBranchTo(b3, NULL); + + Relooper r; + r.AddBlock(b0); + r.AddBlock(b1); + r.AddBlock(b2); + r.AddBlock(b3); + r.AddBlock(b4); + + r.Calculate(b0); + printf("\n\n"); + r.Render(); + + puts(buffer); + + return 1; +} diff --git a/src/relooper/test_fuzz4.txt b/src/relooper/test_fuzz4.txt new file mode 100644 index 00000000..5bb219f4 --- /dev/null +++ b/src/relooper/test_fuzz4.txt @@ -0,0 +1,20 @@ + + +print('entry'); var label; var state; var decisions = [2, 2, 1, 3, 2, 2, 1, 3, 2, 3, 3, 1, 3, 2, 1]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] } +if (state == 2) { + while(1) { + print(2); state = check(); + } +} else { + while(1) { + print(4); state = check(); + if (!(state == 4)) { + break; + } + } + print(3); state = check(); + while(1) { + print(1); state = check(); + } +} + diff --git a/src/relooper/test_fuzz5.cpp b/src/relooper/test_fuzz5.cpp new file mode 100644 index 00000000..f48c31ee --- /dev/null +++ b/src/relooper/test_fuzz5.cpp @@ -0,0 +1,57 @@ + + +#include +#include "Relooper.h" + +int main() { + #define SIZE (10*1024*1024) + char *buffer = (char*)malloc(SIZE); + Relooper::SetOutputBuffer(buffer, SIZE); + + Block *b0 = new Block("print('entry'); var label; var state; var decisions = [133, 98, 134, 143, 162, 187, 130, 87, 91, 49, 102, 47, 9, 132, 179, 176, 157, 25, 64, 161, 57, 107, 16, 167, 185, 45, 191, 180, 23, 131]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] }"); + Block *b1 = new Block("print(1); state = check();"); + Block *b2 = new Block("print(2); state = check();"); + Block *b3 = new Block("print(3); state = check();"); + Block *b4 = new Block("print(4); state = check();"); + Block *b5 = new Block("print(5); state = check();"); + Block *b6 = new Block("print(6); state = check();"); + Block *b7 = new Block("print(7); state = check();"); + Block *b8 = new Block("print(8); state = check();"); + Block *b9 = new Block("print(9); state = check();"); + b0->AddBranchTo(b7, NULL); + b1->AddBranchTo(b4, "state % 2 == 0"); + b1->AddBranchTo(b6, NULL); + b2->AddBranchTo(b1, NULL); + b3->AddBranchTo(b3, NULL); + b4->AddBranchTo(b2, NULL); + b5->AddBranchTo(b1, NULL); + b6->AddBranchTo(b7, "state % 2 == 0"); + b6->AddBranchTo(b6, NULL); + b7->AddBranchTo(b8, "state % 3 == 0"); + b7->AddBranchTo(b2, "state % 3 == 1"); + b7->AddBranchTo(b3, NULL); + b8->AddBranchTo(b4, "state % 2 == 0"); + b8->AddBranchTo(b6, NULL); + b9->AddBranchTo(b7, "state % 2 == 0"); + b9->AddBranchTo(b8, NULL); + + Relooper r; + r.AddBlock(b0); + r.AddBlock(b1); + r.AddBlock(b2); + r.AddBlock(b3); + r.AddBlock(b4); + r.AddBlock(b5); + r.AddBlock(b6); + r.AddBlock(b7); + r.AddBlock(b8); + r.AddBlock(b9); + + r.Calculate(b0); + printf("\n\n"); + r.Render(); + + puts(buffer); + + return 1; +} diff --git a/src/relooper/test_fuzz5.txt b/src/relooper/test_fuzz5.txt new file mode 100644 index 00000000..9548205c --- /dev/null +++ b/src/relooper/test_fuzz5.txt @@ -0,0 +1,56 @@ + + +print('entry'); var label; var state; var decisions = [133, 98, 134, 143, 162, 187, 130, 87, 91, 49, 102, 47, 9, 132, 179, 176, 157, 25, 64, 161, 57, 107, 16, 167, 185, 45, 191, 180, 23, 131]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] } +L1: while(1) { + print(7); state = check(); + do { + if (state % 3 == 1) { + label = 3; + } else if (state % 3 == 0) { + print(8); state = check(); + if (state % 2 == 0) { + label = 5; + break; + } else { + label = 7; + break; + } + } else { + break L1; + } + } while(0); + while(1) { + if (label == 3) { + label = 0; + print(2); state = check(); + print(1); state = check(); + if (state % 2 == 0) { + label = 5; + continue; + } else { + label = 7; + continue; + } + } + else if (label == 5) { + label = 0; + print(4); state = check(); + label = 3; + continue; + } + else if (label == 7) { + label = 0; + print(6); state = check(); + if (state % 2 == 0) { + continue L1; + } else { + label = 7; + continue; + } + } + } +} +while(1) { + print(3); state = check(); +} + diff --git a/src/relooper/test_fuzz6.cpp b/src/relooper/test_fuzz6.cpp new file mode 100644 index 00000000..76a016d6 --- /dev/null +++ b/src/relooper/test_fuzz6.cpp @@ -0,0 +1,322 @@ + + +#include +#include "Relooper.h" + +int main() { + #define SIZE (10*1024*1024) + char *buffer = (char*)malloc(SIZE); + Relooper::SetOutputBuffer(buffer, SIZE); + + Block *b0 = new Block("print('entry'); var label; var state; var decisions = [759, 1223, 618, 1805, 277, 512, 204, 1545, 606, 734, 585, 447, 1670, 1031, 665, 1728, 353, 634, 1033, 13, 658, 589, 474, 854, 405, 1111, 1640, 697, 1156, 1357, 317, 618, 990, 1401, 405, 564, 497, 829, 653, 1194, 25, 322, 1178, 198, 1565, 1419, 1608, 486, 368, 606, 813, 22, 148, 141, 261, 375, 472, 964, 1106, 694, 205, 771, 44, 675, 545, 1027, 1528, 240, 1289, 564, 792, 744, 366, 668, 823, 210, 428, 1009, 1662, 1317, 1183, 681, 14, 1334, 712, 506, 224, 695, 401, 1035, 384, 486, 1519, 122, 1186, 1487, 1819, 1702, 463, 1706, 660, 1642, 847, 991, 976, 940, 867, 46, 23, 1449, 56, 1711, 634, 404, 1558, 168, 710, 1581, 1302, 870, 997, 1295, 1739, 769, 1005, 291, 1638, 1771, 842, 659, 1695, 713, 935, 802, 1173, 1572, 850, 607, 996, 55, 1576, 321, 1815, 662, 1044, 1612, 1680, 1050, 844, 553, 278, 1447, 1662, 1094, 1797, 774, 1013, 1204, 907, 340, 1172, 1460, 869, 1264, 111, 1176, 484, 845, 258, 417, 1246, 1017, 745, 189, 333, 1658, 1395, 1764, 1786, 165, 404, 847, 1429, 1574, 403, 718, 1118, 1756, 94, 56, 1498, 1696, 1355, 840, 50, 82, 371, 1087, 875, 1337, 267, 958, 1209, 1167, 1025, 1684, 184, 962, 1496, 201, 127, 372, 1, 1005, 402, 1387, 213, 1143, 1271, 167, 10, 12, 1060, 1390, 1366, 893, 747, 1005, 481, 876, 227, 514, 589, 250, 273, 1188, 1052, 719, 219, 1006, 38, 120, 1454, 489, 672, 149, 534, 1081, 1721, 586, 330, 25, 356, 1743, 1607, 336, 981, 419, 1036, 1293, 1026, 1300, 1453, 792, 22, 45, 420, 409, 1027, 1437, 1421, 795, 136, 1276, 1610, 1593]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] }"); + Block *b1 = new Block("print(1); state = check();// ..........................................................................."); + Block *b2 = new Block("print(2); state = check();// ........."); + Block *b3 = new Block("print(3); state = check();// .................................."); + Block *b4 = new Block("print(4); state = check();// ..........................................................................................................................."); + Block *b5 = new Block("print(5); state = check();// .........................................................................................................................................."); + Block *b6 = new Block("print(6); state = check();// ........."); + Block *b7 = new Block("print(7); state = check();// ............................................................................................................................................................................................."); + Block *b8 = new Block("print(8); state = check();// ...................................................................................................................................................................................................................................................."); + Block *b9 = new Block("print(9); state = check();// ..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................."); + Block *b10 = new Block("print(10); state = check();// ..................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................."); + Block *b11 = new Block("print(11); state = check();// ........................................................"); + Block *b12 = new Block("print(12); state = check();// ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................"); + Block *b13 = new Block("print(13); state = check();// ..................."); + Block *b14 = new Block("print(14); state = check();// ............................."); + Block *b15 = new Block("print(15); state = check();// .................................................."); + Block *b16 = new Block("print(16); state = check();// ................................................................................................................................................................................................................................................................................................................................................................"); + Block *b17 = new Block("print(17); state = check();// ................................................................"); + Block *b18 = new Block("print(18); state = check();// .............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................."); + Block *b19 = new Block("print(19); state = check();// ......................................................................................................................................................................................................................"); + Block *b20 = new Block("print(20); state = check();// .................................................................................................................................................................."); + Block *b21 = new Block("print(21); state = check();// ..........................."); + Block *b22 = new Block("print(22); state = check();// ........................................................................................................."); + Block *b23 = new Block("print(23); state = check();// ................................................................................................................................................................................................................."); + Block *b24 = new Block("print(24); state = check();// ..........................."); + Block *b25 = new Block("print(25); state = check();// ......................................................................................................................................................"); + Block *b26 = new Block("print(26); state = check();// ........................................................................................................................................................................................................................................................................."); + Block *b27 = new Block("print(27); state = check();// ............................................................................................................................................................................."); + Block *b28 = new Block("print(28); state = check();// .............................................................................................................."); + Block *b29 = new Block("print(29); state = check();// ..............."); + Block *b30 = new Block("print(30); state = check();// ................................................................................................................................................................................................................."); + Block *b31 = new Block("print(31); state = check();// .........................................................................................................................................................................................................."); + Block *b32 = new Block("print(32); state = check();// ......................................................................................................"); + Block *b33 = new Block("print(33); state = check();// ...."); + Block *b34 = new Block("print(34); state = check();// .........................................................................................................................................."); + Block *b35 = new Block("print(35); state = check();// ................................."); + Block *b36 = new Block("print(36); state = check();// ........................."); + Block *b37 = new Block("print(37); state = check();// ................................................................................................................................"); + Block *b38 = new Block("print(38); state = check();// ............................................................................................................................................................................................................................................................................................................................................"); + Block *b39 = new Block("print(39); state = check();// ................"); + Block *b40 = new Block("print(40); state = check();// ................................................................................................................................................"); + Block *b41 = new Block("print(41); state = check();// ..................................................................................................................................."); + Block *b42 = new Block("print(42); state = check();// ....................................................."); + Block *b43 = new Block("print(43); state = check();// ........."); + Block *b44 = new Block("print(44); state = check();// ....................................................................................................................................................."); + Block *b45 = new Block("print(45); state = check();// ............................"); + Block *b46 = new Block("print(46); state = check();// ............................................................................."); + Block *b47 = new Block("print(47); state = check();// ...................................................................................................................................."); + Block *b48 = new Block("print(48); state = check();// ............"); + Block *b49 = new Block("print(49); state = check();// ............................................................................................................................................................................................................................................................................................"); + Block *b50 = new Block("print(50); state = check();// ........................................"); + Block *b51 = new Block("print(51); state = check();// ............................................................................................."); + Block *b52 = new Block("print(52); state = check();// .............................................................................."); + Block *b53 = new Block("print(53); state = check();// .............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................."); + Block *b54 = new Block("print(54); state = check();// ....................................."); + Block *b55 = new Block("print(55); state = check();// ..........................................................................................................................................................................................................."); + Block *b56 = new Block("print(56); state = check();// ...................................................................................................................................................................................................................."); + Block *b57 = new Block("print(57); state = check();// ..........................................................................................................................................................................................................................................................................................................................."); + Block *b58 = new Block("print(58); state = check();// ......................................................................................"); + Block *b59 = new Block("print(59); state = check();// ..................................."); + Block *b60 = new Block("print(60); state = check();// ......................................................................................................................................................................................................................................"); + Block *b61 = new Block("print(61); state = check();// ........................................................................................................................................................."); + Block *b62 = new Block("print(62); state = check();// ......................................................................................."); + Block *b63 = new Block("print(63); state = check();// ....................................................................................................................................................................."); + Block *b64 = new Block("print(64); state = check();// ......................................................................................................................................................................................................................................................................."); + Block *b65 = new Block("print(65); state = check();// ........................................................."); + Block *b66 = new Block("print(66); state = check();// ..............................................................................................................."); + Block *b67 = new Block("print(67); state = check();// ....................................................................................................................................................................................................................."); + Block *b68 = new Block("print(68); state = check();// ......................................................................................................................................................................................................................................................................................................................"); + Block *b69 = new Block("print(69); state = check();// ......................................................................................................................................................"); + Block *b70 = new Block("print(70); state = check();// .........................................................................................................................."); + Block *b71 = new Block("print(71); state = check();// ..........................................................................................................................................................................................................."); + Block *b72 = new Block("print(72); state = check();// .........................................................................................................."); + Block *b73 = new Block("print(73); state = check();// ."); + Block *b74 = new Block("print(74); state = check();// .............................................."); + Block *b75 = new Block("print(75); state = check();// ............................................."); + Block *b76 = new Block("print(76); state = check();// .............................................................................................................................................................................................................................................................................................................................................................................................................................."); + Block *b77 = new Block("print(77); state = check();// ..........................................................................................................................................................................................................................................................................................."); + Block *b78 = new Block("print(78); state = check();// .........................................................................................."); + Block *b79 = new Block("print(79); state = check();// ..................................................................................................................................................................................................................................................."); + Block *b80 = new Block("print(80); state = check();// ...................................."); + Block *b81 = new Block("print(81); state = check();// ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................"); + Block *b82 = new Block("print(82); state = check();// ...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................."); + Block *b83 = new Block("print(83); state = check();// ........................................................................................"); + Block *b84 = new Block("print(84); state = check();// ..................."); + Block *b85 = new Block("print(85); state = check();// ........................................................................................................................................................................................................................................................................................................................................................."); + Block *b86 = new Block("print(86); state = check();// ................................................................................................................................................................................................................................................."); + Block *b87 = new Block("print(87); state = check();// ......"); + Block *b88 = new Block("print(88); state = check();// ...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................."); + Block *b89 = new Block("print(89); state = check();// ......................................................................................................................................................................................................................................................................................................................................................"); + Block *b90 = new Block("print(90); state = check();// ..........................................................................................................................................................................................................................."); + Block *b91 = new Block("print(91); state = check();// .............................................."); + b0->AddBranchTo(b30, NULL); + b1->AddBranchTo(b66, NULL); + b2->AddBranchTo(b51, NULL); + b3->AddBranchTo(b57, NULL); + b4->AddBranchTo(b31, NULL); + b5->AddBranchTo(b21, NULL); + b6->AddBranchTo(b88, NULL); + b7->AddBranchTo(b75, "state % 2 == 0"); + b7->AddBranchTo(b89, NULL); + b8->AddBranchTo(b47, "state % 2 == 0"); + b8->AddBranchTo(b19, NULL); + b9->AddBranchTo(b66, NULL); + b10->AddBranchTo(b52, NULL); + b11->AddBranchTo(b40, NULL); + b12->AddBranchTo(b87, NULL); + b13->AddBranchTo(b72, "state % 3 == 0"); + b13->AddBranchTo(b6, "state % 3 == 1"); + b13->AddBranchTo(b55, NULL); + b14->AddBranchTo(b2, "state % 2 == 0"); + b14->AddBranchTo(b52, NULL); + b15->AddBranchTo(b11, NULL); + b16->AddBranchTo(b57, NULL); + b17->AddBranchTo(b1, "state % 2 == 0"); + b17->AddBranchTo(b24, NULL); + b18->AddBranchTo(b67, NULL); + b19->AddBranchTo(b56, NULL); + b20->AddBranchTo(b34, NULL); + b21->AddBranchTo(b25, NULL); + b22->AddBranchTo(b72, NULL); + b23->AddBranchTo(b64, NULL); + b24->AddBranchTo(b36, NULL); + b25->AddBranchTo(b88, NULL); + b26->AddBranchTo(b56, NULL); + b27->AddBranchTo(b3, NULL); + b28->AddBranchTo(b75, NULL); + b29->AddBranchTo(b8, NULL); + b30->AddBranchTo(b58, "state % 3 == 0"); + b30->AddBranchTo(b66, "state % 3 == 1"); + b30->AddBranchTo(b6, NULL); + b31->AddBranchTo(b60, NULL); + b32->AddBranchTo(b83, NULL); + b33->AddBranchTo(b60, NULL); + b34->AddBranchTo(b73, NULL); + b35->AddBranchTo(b7, NULL); + b36->AddBranchTo(b60, "state % 2 == 0"); + b36->AddBranchTo(b16, NULL); + b37->AddBranchTo(b82, NULL); + b38->AddBranchTo(b45, NULL); + b39->AddBranchTo(b72, "state % 3 == 0"); + b39->AddBranchTo(b73, "state % 3 == 1"); + b39->AddBranchTo(b31, NULL); + b40->AddBranchTo(b89, NULL); + b41->AddBranchTo(b64, "state % 2 == 0"); + b41->AddBranchTo(b90, NULL); + b42->AddBranchTo(b12, NULL); + b43->AddBranchTo(b32, NULL); + b44->AddBranchTo(b28, NULL); + b45->AddBranchTo(b63, "state % 2 == 0"); + b45->AddBranchTo(b47, NULL); + b46->AddBranchTo(b70, "state % 2 == 0"); + b46->AddBranchTo(b42, NULL); + b47->AddBranchTo(b28, NULL); + b48->AddBranchTo(b20, "state % 2 == 0"); + b48->AddBranchTo(b91, NULL); + b49->AddBranchTo(b6, NULL); + b50->AddBranchTo(b29, NULL); + b51->AddBranchTo(b36, NULL); + b52->AddBranchTo(b61, "state % 2 == 0"); + b52->AddBranchTo(b2, NULL); + b53->AddBranchTo(b75, "state % 2 == 0"); + b53->AddBranchTo(b46, NULL); + b54->AddBranchTo(b30, NULL); + b55->AddBranchTo(b59, NULL); + b56->AddBranchTo(b34, NULL); + b57->AddBranchTo(b39, NULL); + b58->AddBranchTo(b30, NULL); + b59->AddBranchTo(b47, NULL); + b60->AddBranchTo(b10, NULL); + b61->AddBranchTo(b88, NULL); + b62->AddBranchTo(b36, NULL); + b63->AddBranchTo(b54, NULL); + b64->AddBranchTo(b79, NULL); + b65->AddBranchTo(b65, NULL); + b66->AddBranchTo(b6, NULL); + b67->AddBranchTo(b78, NULL); + b68->AddBranchTo(b51, NULL); + b69->AddBranchTo(b32, NULL); + b70->AddBranchTo(b47, NULL); + b71->AddBranchTo(b38, NULL); + b72->AddBranchTo(b91, "state % 2 == 0"); + b72->AddBranchTo(b80, NULL); + b73->AddBranchTo(b62, "state % 3 == 0"); + b73->AddBranchTo(b31, "state % 3 == 1"); + b73->AddBranchTo(b43, NULL); + b74->AddBranchTo(b77, NULL); + b75->AddBranchTo(b7, NULL); + b76->AddBranchTo(b22, NULL); + b77->AddBranchTo(b76, NULL); + b78->AddBranchTo(b14, "state % 2 == 0"); + b78->AddBranchTo(b62, NULL); + b79->AddBranchTo(b81, NULL); + b80->AddBranchTo(b51, "state % 2 == 0"); + b80->AddBranchTo(b50, NULL); + b81->AddBranchTo(b40, NULL); + b82->AddBranchTo(b60, "state % 2 == 0"); + b82->AddBranchTo(b43, NULL); + b83->AddBranchTo(b77, NULL); + b84->AddBranchTo(b60, "state % 2 == 0"); + b84->AddBranchTo(b77, NULL); + b85->AddBranchTo(b42, NULL); + b86->AddBranchTo(b85, "state % 2 == 0"); + b86->AddBranchTo(b88, NULL); + b87->AddBranchTo(b88, NULL); + b88->AddBranchTo(b70, NULL); + b89->AddBranchTo(b68, NULL); + b90->AddBranchTo(b33, NULL); + b91->AddBranchTo(b33, NULL); + + Relooper r; + r.AddBlock(b0); + r.AddBlock(b1); + r.AddBlock(b2); + r.AddBlock(b3); + r.AddBlock(b4); + r.AddBlock(b5); + r.AddBlock(b6); + r.AddBlock(b7); + r.AddBlock(b8); + r.AddBlock(b9); + r.AddBlock(b10); + r.AddBlock(b11); + r.AddBlock(b12); + r.AddBlock(b13); + r.AddBlock(b14); + r.AddBlock(b15); + r.AddBlock(b16); + r.AddBlock(b17); + r.AddBlock(b18); + r.AddBlock(b19); + r.AddBlock(b20); + r.AddBlock(b21); + r.AddBlock(b22); + r.AddBlock(b23); + r.AddBlock(b24); + r.AddBlock(b25); + r.AddBlock(b26); + r.AddBlock(b27); + r.AddBlock(b28); + r.AddBlock(b29); + r.AddBlock(b30); + r.AddBlock(b31); + r.AddBlock(b32); + r.AddBlock(b33); + r.AddBlock(b34); + r.AddBlock(b35); + r.AddBlock(b36); + r.AddBlock(b37); + r.AddBlock(b38); + r.AddBlock(b39); + r.AddBlock(b40); + r.AddBlock(b41); + r.AddBlock(b42); + r.AddBlock(b43); + r.AddBlock(b44); + r.AddBlock(b45); + r.AddBlock(b46); + r.AddBlock(b47); + r.AddBlock(b48); + r.AddBlock(b49); + r.AddBlock(b50); + r.AddBlock(b51); + r.AddBlock(b52); + r.AddBlock(b53); + r.AddBlock(b54); + r.AddBlock(b55); + r.AddBlock(b56); + r.AddBlock(b57); + r.AddBlock(b58); + r.AddBlock(b59); + r.AddBlock(b60); + r.AddBlock(b61); + r.AddBlock(b62); + r.AddBlock(b63); + r.AddBlock(b64); + r.AddBlock(b65); + r.AddBlock(b66); + r.AddBlock(b67); + r.AddBlock(b68); + r.AddBlock(b69); + r.AddBlock(b70); + r.AddBlock(b71); + r.AddBlock(b72); + r.AddBlock(b73); + r.AddBlock(b74); + r.AddBlock(b75); + r.AddBlock(b76); + r.AddBlock(b77); + r.AddBlock(b78); + r.AddBlock(b79); + r.AddBlock(b80); + r.AddBlock(b81); + r.AddBlock(b82); + r.AddBlock(b83); + r.AddBlock(b84); + r.AddBlock(b85); + r.AddBlock(b86); + r.AddBlock(b87); + r.AddBlock(b88); + r.AddBlock(b89); + r.AddBlock(b90); + r.AddBlock(b91); + + r.Calculate(b0); + printf("\n\n"); + r.Render(); + + puts(buffer); + + return 1; +} diff --git a/src/relooper/test_fuzz6.txt b/src/relooper/test_fuzz6.txt new file mode 100644 index 00000000..af188ab1 --- /dev/null +++ b/src/relooper/test_fuzz6.txt @@ -0,0 +1,116 @@ + + +print('entry'); var label; var state; var decisions = [759, 1223, 618, 1805, 277, 512, 204, 1545, 606, 734, 585, 447, 1670, 1031, 665, 1728, 353, 634, 1033, 13, 658, 589, 474, 854, 405, 1111, 1640, 697, 1156, 1357, 317, 618, 990, 1401, 405, 564, 497, 829, 653, 1194, 25, 322, 1178, 198, 1565, 1419, 1608, 486, 368, 606, 813, 22, 148, 141, 261, 375, 472, 964, 1106, 694, 205, 771, 44, 675, 545, 1027, 1528, 240, 1289, 564, 792, 744, 366, 668, 823, 210, 428, 1009, 1662, 1317, 1183, 681, 14, 1334, 712, 506, 224, 695, 401, 1035, 384, 486, 1519, 122, 1186, 1487, 1819, 1702, 463, 1706, 660, 1642, 847, 991, 976, 940, 867, 46, 23, 1449, 56, 1711, 634, 404, 1558, 168, 710, 1581, 1302, 870, 997, 1295, 1739, 769, 1005, 291, 1638, 1771, 842, 659, 1695, 713, 935, 802, 1173, 1572, 850, 607, 996, 55, 1576, 321, 1815, 662, 1044, 1612, 1680, 1050, 844, 553, 278, 1447, 1662, 1094, 1797, 774, 1013, 1204, 907, 340, 1172, 1460, 869, 1264, 111, 1176, 484, 845, 258, 417, 1246, 1017, 745, 189, 333, 1658, 1395, 1764, 1786, 165, 404, 847, 1429, 1574, 403, 718, 1118, 1756, 94, 56, 1498, 1696, 1355, 840, 50, 82, 371, 1087, 875, 1337, 267, 958, 1209, 1167, 1025, 1684, 184, 962, 1496, 201, 127, 372, 1, 1005, 402, 1387, 213, 1143, 1271, 167, 10, 12, 1060, 1390, 1366, 893, 747, 1005, 481, 876, 227, 514, 589, 250, 273, 1188, 1052, 719, 219, 1006, 38, 120, 1454, 489, 672, 149, 534, 1081, 1721, 586, 330, 25, 356, 1743, 1607, 336, 981, 419, 1036, 1293, 1026, 1300, 1453, 792, 22, 45, 420, 409, 1027, 1437, 1421, 795, 136, 1276, 1610, 1593]; var index = 0; function check() { if (index == decisions.length) throw 'HALT'; return decisions[index++] } +while(1) { + print(30); state = check();// ................................................................................................................................................................................................................. + if (state % 3 == 1) { + label = 67; + break; + } else if (!(state % 3 == 0)) { + break; + } + print(58); state = check();// ...................................................................................... +} +if (label == 67) { + print(66); state = check();// ............................................................................................................... +} +print(6); state = check();// ......... +while(1) { + print(88); state = check();// .................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... + print(70); state = check();// .......................................................................................................................... + L10: while(1) { + print(47); state = check();// .................................................................................................................................... + print(28); state = check();// .............................................................................................................. + while(1) { + print(75); state = check();// ............................................. + print(7); state = check();// ............................................................................................................................................................................................. + if (!(state % 2 == 0)) { + break; + } + } + print(89); state = check();// ...................................................................................................................................................................................................................................................................................................................................................... + print(68); state = check();// ...................................................................................................................................................................................................................................................................................................................... + L18: while(1) { + print(51); state = check();// ............................................................................................. + L20: while(1) { + print(36); state = check();// ......................... + if (state % 2 == 0) { + break; + } + print(16); state = check();// ................................................................................................................................................................................................................................................................................................................................................................ + print(57); state = check();// ........................................................................................................................................................................................................................................................................................................................... + print(39); state = check();// ................ + if (state % 3 == 0) { + label = 73; + } else if (state % 3 == 1) { + label = 74; + } else { + label = 32; + break; + } + while(1) { + if (label == 73) { + label = 0; + print(72); state = check();// .......................................................................................................... + if (state % 2 == 0) { + label = 92; + break L20; + } + print(80); state = check();// .................................... + if (state % 2 == 0) { + continue L18; + } + print(50); state = check();// ........................................ + print(29); state = check();// ............... + print(8); state = check();// .................................................................................................................................................................................................................................................... + if (state % 2 == 0) { + continue L10; + } + print(19); state = check();// ...................................................................................................................................................................................................................... + print(56); state = check();// .................................................................................................................................................................................................................... + print(34); state = check();// .......................................................................................................................................... + label = 74; + continue; + } + else if (label == 74) { + label = 0; + print(73); state = check();// . + if (state % 3 == 1) { + label = 32; + break L20; + } else if (state % 3 == 0) { + break; + } + print(43); state = check();// ......... + print(32); state = check();// ...................................................................................................... + print(83); state = check();// ........................................................................................ + print(77); state = check();// ........................................................................................................................................................................................................................................................................................... + print(76); state = check();// .............................................................................................................................................................................................................................................................................................................................................................................................................................. + print(22); state = check();// ......................................................................................................... + label = 73; + continue; + } + } + print(62); state = check();// ....................................................................................... + } + if (label == 32) { + label = 0; + print(31); state = check();// .......................................................................................................................................................................................................... + } + else if (label == 92) { + label = 0; + print(91); state = check();// .............................................. + print(33); state = check();// .... + } + print(60); state = check();// ...................................................................................................................................................................................................................................... + print(10); state = check();// ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... + print(52); state = check();// .............................................................................. + if (state % 2 == 0) { + break L10; + } + print(2); state = check();// ......... + } + } + print(61); state = check();// ......................................................................................................................................................... +} + diff --git a/src/relooper/test_inf.cpp b/src/relooper/test_inf.cpp new file mode 100644 index 00000000..66e712ed --- /dev/null +++ b/src/relooper/test_inf.cpp @@ -0,0 +1,813 @@ +#include "Relooper.h" +int main() { + void *block_map[10000]; + void *rl = rl_new_relooper(); + char buffer[100000]; + rl_set_output_buffer(buffer, sizeof(buffer)); + void *b0 = rl_new_block("code 0"); + block_map[0] = b0; + rl_relooper_add_block(rl, block_map[0]); + void *b1 = rl_new_block("code 1"); + block_map[1] = b1; + rl_relooper_add_block(rl, block_map[1]); + void *b2 = rl_new_block("code 2"); + block_map[2] = b2; + rl_relooper_add_block(rl, block_map[2]); + void *b3 = rl_new_block("code 3"); + block_map[3] = b3; + rl_relooper_add_block(rl, block_map[3]); + void *b4 = rl_new_block("code 4"); + block_map[4] = b4; + rl_relooper_add_block(rl, block_map[4]); + void *b5 = rl_new_block("code 5"); + block_map[5] = b5; + rl_relooper_add_block(rl, block_map[5]); + void *b6 = rl_new_block("code 6"); + block_map[6] = b6; + rl_relooper_add_block(rl, block_map[6]); + void *b7 = rl_new_block("code 7"); + block_map[7] = b7; + rl_relooper_add_block(rl, block_map[7]); + void *b8 = rl_new_block("code 8"); + block_map[8] = b8; + rl_relooper_add_block(rl, block_map[8]); + void *b9 = rl_new_block("code 9"); + block_map[9] = b9; + rl_relooper_add_block(rl, block_map[9]); + void *b10 = rl_new_block("code 10"); + block_map[10] = b10; + rl_relooper_add_block(rl, block_map[10]); + void *b11 = rl_new_block("code 11"); + block_map[11] = b11; + rl_relooper_add_block(rl, block_map[11]); + void *b12 = rl_new_block("code 12"); + block_map[12] = b12; + rl_relooper_add_block(rl, block_map[12]); + void *b13 = rl_new_block("code 13"); + block_map[13] = b13; + rl_relooper_add_block(rl, block_map[13]); + void *b14 = rl_new_block("code 14"); + block_map[14] = b14; + rl_relooper_add_block(rl, block_map[14]); + void *b15 = rl_new_block("code 15"); + block_map[15] = b15; + rl_relooper_add_block(rl, block_map[15]); + void *b16 = rl_new_block("code 16"); + block_map[16] = b16; + rl_relooper_add_block(rl, block_map[16]); + void *b17 = rl_new_block("code 17"); + block_map[17] = b17; + rl_relooper_add_block(rl, block_map[17]); + void *b18 = rl_new_block("code 18"); + block_map[18] = b18; + rl_relooper_add_block(rl, block_map[18]); + void *b19 = rl_new_block("code 19"); + block_map[19] = b19; + rl_relooper_add_block(rl, block_map[19]); + void *b20 = rl_new_block("code 20"); + block_map[20] = b20; + rl_relooper_add_block(rl, block_map[20]); + void *b21 = rl_new_block("code 21"); + block_map[21] = b21; + rl_relooper_add_block(rl, block_map[21]); + void *b22 = rl_new_block("code 22"); + block_map[22] = b22; + rl_relooper_add_block(rl, block_map[22]); + void *b23 = rl_new_block("code 23"); + block_map[23] = b23; + rl_relooper_add_block(rl, block_map[23]); + void *b24 = rl_new_block("code 24"); + block_map[24] = b24; + rl_relooper_add_block(rl, block_map[24]); + void *b25 = rl_new_block("code 25"); + block_map[25] = b25; + rl_relooper_add_block(rl, block_map[25]); + void *b26 = rl_new_block("code 26"); + block_map[26] = b26; + rl_relooper_add_block(rl, block_map[26]); + void *b27 = rl_new_block("code 27"); + block_map[27] = b27; + rl_relooper_add_block(rl, block_map[27]); + void *b28 = rl_new_block("code 28"); + block_map[28] = b28; + rl_relooper_add_block(rl, block_map[28]); + void *b29 = rl_new_block("code 29"); + block_map[29] = b29; + rl_relooper_add_block(rl, block_map[29]); + void *b30 = rl_new_block("code 30"); + block_map[30] = b30; + rl_relooper_add_block(rl, block_map[30]); + void *b31 = rl_new_block("code 31"); + block_map[31] = b31; + rl_relooper_add_block(rl, block_map[31]); + void *b32 = rl_new_block("code 32"); + block_map[32] = b32; + rl_relooper_add_block(rl, block_map[32]); + void *b33 = rl_new_block("code 33"); + block_map[33] = b33; + rl_relooper_add_block(rl, block_map[33]); + void *b34 = rl_new_block("code 34"); + block_map[34] = b34; + rl_relooper_add_block(rl, block_map[34]); + void *b35 = rl_new_block("code 35"); + block_map[35] = b35; + rl_relooper_add_block(rl, block_map[35]); + void *b36 = rl_new_block("code 36"); + block_map[36] = b36; + rl_relooper_add_block(rl, block_map[36]); + void *b37 = rl_new_block("code 37"); + block_map[37] = b37; + rl_relooper_add_block(rl, block_map[37]); + void *b38 = rl_new_block("code 38"); + block_map[38] = b38; + rl_relooper_add_block(rl, block_map[38]); + void *b39 = rl_new_block("code 39"); + block_map[39] = b39; + rl_relooper_add_block(rl, block_map[39]); + void *b40 = rl_new_block("code 40"); + block_map[40] = b40; + rl_relooper_add_block(rl, block_map[40]); + void *b41 = rl_new_block("code 41"); + block_map[41] = b41; + rl_relooper_add_block(rl, block_map[41]); + void *b42 = rl_new_block("code 42"); + block_map[42] = b42; + rl_relooper_add_block(rl, block_map[42]); + void *b43 = rl_new_block("code 43"); + block_map[43] = b43; + rl_relooper_add_block(rl, block_map[43]); + void *b44 = rl_new_block("code 44"); + block_map[44] = b44; + rl_relooper_add_block(rl, block_map[44]); + void *b45 = rl_new_block("code 45"); + block_map[45] = b45; + rl_relooper_add_block(rl, block_map[45]); + void *b46 = rl_new_block("code 46"); + block_map[46] = b46; + rl_relooper_add_block(rl, block_map[46]); + void *b47 = rl_new_block("code 47"); + block_map[47] = b47; + rl_relooper_add_block(rl, block_map[47]); + void *b48 = rl_new_block("code 48"); + block_map[48] = b48; + rl_relooper_add_block(rl, block_map[48]); + void *b49 = rl_new_block("code 49"); + block_map[49] = b49; + rl_relooper_add_block(rl, block_map[49]); + void *b50 = rl_new_block("code 50"); + block_map[50] = b50; + rl_relooper_add_block(rl, block_map[50]); + void *b51 = rl_new_block("code 51"); + block_map[51] = b51; + rl_relooper_add_block(rl, block_map[51]); + void *b52 = rl_new_block("code 52"); + block_map[52] = b52; + rl_relooper_add_block(rl, block_map[52]); + void *b53 = rl_new_block("code 53"); + block_map[53] = b53; + rl_relooper_add_block(rl, block_map[53]); + void *b54 = rl_new_block("code 54"); + block_map[54] = b54; + rl_relooper_add_block(rl, block_map[54]); + void *b55 = rl_new_block("code 55"); + block_map[55] = b55; + rl_relooper_add_block(rl, block_map[55]); + void *b56 = rl_new_block("code 56"); + block_map[56] = b56; + rl_relooper_add_block(rl, block_map[56]); + void *b57 = rl_new_block("code 57"); + block_map[57] = b57; + rl_relooper_add_block(rl, block_map[57]); + void *b58 = rl_new_block("code 58"); + block_map[58] = b58; + rl_relooper_add_block(rl, block_map[58]); + void *b59 = rl_new_block("code 59"); + block_map[59] = b59; + rl_relooper_add_block(rl, block_map[59]); + void *b60 = rl_new_block("code 60"); + block_map[60] = b60; + rl_relooper_add_block(rl, block_map[60]); + void *b61 = rl_new_block("code 61"); + block_map[61] = b61; + rl_relooper_add_block(rl, block_map[61]); + void *b62 = rl_new_block("code 62"); + block_map[62] = b62; + rl_relooper_add_block(rl, block_map[62]); + void *b63 = rl_new_block("code 63"); + block_map[63] = b63; + rl_relooper_add_block(rl, block_map[63]); + void *b64 = rl_new_block("code 64"); + block_map[64] = b64; + rl_relooper_add_block(rl, block_map[64]); + void *b65 = rl_new_block("code 65"); + block_map[65] = b65; + rl_relooper_add_block(rl, block_map[65]); + void *b66 = rl_new_block("code 66"); + block_map[66] = b66; + rl_relooper_add_block(rl, block_map[66]); + void *b67 = rl_new_block("code 67"); + block_map[67] = b67; + rl_relooper_add_block(rl, block_map[67]); + void *b68 = rl_new_block("code 68"); + block_map[68] = b68; + rl_relooper_add_block(rl, block_map[68]); + void *b69 = rl_new_block("code 69"); + block_map[69] = b69; + rl_relooper_add_block(rl, block_map[69]); + void *b70 = rl_new_block("code 70"); + block_map[70] = b70; + rl_relooper_add_block(rl, block_map[70]); + void *b71 = rl_new_block("code 71"); + block_map[71] = b71; + rl_relooper_add_block(rl, block_map[71]); + void *b72 = rl_new_block("code 72"); + block_map[72] = b72; + rl_relooper_add_block(rl, block_map[72]); + void *b73 = rl_new_block("code 73"); + block_map[73] = b73; + rl_relooper_add_block(rl, block_map[73]); + void *b74 = rl_new_block("code 74"); + block_map[74] = b74; + rl_relooper_add_block(rl, block_map[74]); + void *b75 = rl_new_block("code 75"); + block_map[75] = b75; + rl_relooper_add_block(rl, block_map[75]); + void *b76 = rl_new_block("code 76"); + block_map[76] = b76; + rl_relooper_add_block(rl, block_map[76]); + void *b77 = rl_new_block("code 77"); + block_map[77] = b77; + rl_relooper_add_block(rl, block_map[77]); + void *b78 = rl_new_block("code 78"); + block_map[78] = b78; + rl_relooper_add_block(rl, block_map[78]); + void *b79 = rl_new_block("code 79"); + block_map[79] = b79; + rl_relooper_add_block(rl, block_map[79]); + void *b80 = rl_new_block("code 80"); + block_map[80] = b80; + rl_relooper_add_block(rl, block_map[80]); + void *b81 = rl_new_block("code 81"); + block_map[81] = b81; + rl_relooper_add_block(rl, block_map[81]); + void *b82 = rl_new_block("code 82"); + block_map[82] = b82; + rl_relooper_add_block(rl, block_map[82]); + void *b83 = rl_new_block("code 83"); + block_map[83] = b83; + rl_relooper_add_block(rl, block_map[83]); + void *b84 = rl_new_block("code 84"); + block_map[84] = b84; + rl_relooper_add_block(rl, block_map[84]); + void *b85 = rl_new_block("code 85"); + block_map[85] = b85; + rl_relooper_add_block(rl, block_map[85]); + void *b86 = rl_new_block("code 86"); + block_map[86] = b86; + rl_relooper_add_block(rl, block_map[86]); + void *b87 = rl_new_block("code 87"); + block_map[87] = b87; + rl_relooper_add_block(rl, block_map[87]); + void *b88 = rl_new_block("code 88"); + block_map[88] = b88; + rl_relooper_add_block(rl, block_map[88]); + void *b89 = rl_new_block("code 89"); + block_map[89] = b89; + rl_relooper_add_block(rl, block_map[89]); + void *b90 = rl_new_block("code 90"); + block_map[90] = b90; + rl_relooper_add_block(rl, block_map[90]); + void *b91 = rl_new_block("code 91"); + block_map[91] = b91; + rl_relooper_add_block(rl, block_map[91]); + void *b92 = rl_new_block("code 92"); + block_map[92] = b92; + rl_relooper_add_block(rl, block_map[92]); + void *b93 = rl_new_block("code 93"); + block_map[93] = b93; + rl_relooper_add_block(rl, block_map[93]); + void *b94 = rl_new_block("code 94"); + block_map[94] = b94; + rl_relooper_add_block(rl, block_map[94]); + void *b95 = rl_new_block("code 95"); + block_map[95] = b95; + rl_relooper_add_block(rl, block_map[95]); + void *b96 = rl_new_block("code 96"); + block_map[96] = b96; + rl_relooper_add_block(rl, block_map[96]); + void *b97 = rl_new_block("code 97"); + block_map[97] = b97; + rl_relooper_add_block(rl, block_map[97]); + void *b98 = rl_new_block("code 98"); + block_map[98] = b98; + rl_relooper_add_block(rl, block_map[98]); + void *b99 = rl_new_block("code 99"); + block_map[99] = b99; + rl_relooper_add_block(rl, block_map[99]); + void *b100 = rl_new_block("code 100"); + block_map[100] = b100; + rl_relooper_add_block(rl, block_map[100]); + void *b101 = rl_new_block("code 101"); + block_map[101] = b101; + rl_relooper_add_block(rl, block_map[101]); + void *b102 = rl_new_block("code 102"); + block_map[102] = b102; + rl_relooper_add_block(rl, block_map[102]); + void *b103 = rl_new_block("code 103"); + block_map[103] = b103; + rl_relooper_add_block(rl, block_map[103]); + void *b104 = rl_new_block("code 104"); + block_map[104] = b104; + rl_relooper_add_block(rl, block_map[104]); + void *b105 = rl_new_block("code 105"); + block_map[105] = b105; + rl_relooper_add_block(rl, block_map[105]); + void *b106 = rl_new_block("code 106"); + block_map[106] = b106; + rl_relooper_add_block(rl, block_map[106]); + void *b107 = rl_new_block("code 107"); + block_map[107] = b107; + rl_relooper_add_block(rl, block_map[107]); + void *b108 = rl_new_block("code 108"); + block_map[108] = b108; + rl_relooper_add_block(rl, block_map[108]); + void *b109 = rl_new_block("code 109"); + block_map[109] = b109; + rl_relooper_add_block(rl, block_map[109]); + void *b110 = rl_new_block("code 110"); + block_map[110] = b110; + rl_relooper_add_block(rl, block_map[110]); + void *b111 = rl_new_block("code 111"); + block_map[111] = b111; + rl_relooper_add_block(rl, block_map[111]); + void *b112 = rl_new_block("code 112"); + block_map[112] = b112; + rl_relooper_add_block(rl, block_map[112]); + void *b113 = rl_new_block("code 113"); + block_map[113] = b113; + rl_relooper_add_block(rl, block_map[113]); + void *b114 = rl_new_block("code 114"); + block_map[114] = b114; + rl_relooper_add_block(rl, block_map[114]); + void *b115 = rl_new_block("code 115"); + block_map[115] = b115; + rl_relooper_add_block(rl, block_map[115]); + void *b116 = rl_new_block("code 116"); + block_map[116] = b116; + rl_relooper_add_block(rl, block_map[116]); + void *b117 = rl_new_block("code 117"); + block_map[117] = b117; + rl_relooper_add_block(rl, block_map[117]); + void *b118 = rl_new_block("code 118"); + block_map[118] = b118; + rl_relooper_add_block(rl, block_map[118]); + void *b119 = rl_new_block("code 119"); + block_map[119] = b119; + rl_relooper_add_block(rl, block_map[119]); + void *b120 = rl_new_block("code 120"); + block_map[120] = b120; + rl_relooper_add_block(rl, block_map[120]); + void *b121 = rl_new_block("code 121"); + block_map[121] = b121; + rl_relooper_add_block(rl, block_map[121]); + void *b122 = rl_new_block("code 122"); + block_map[122] = b122; + rl_relooper_add_block(rl, block_map[122]); + void *b123 = rl_new_block("code 123"); + block_map[123] = b123; + rl_relooper_add_block(rl, block_map[123]); + void *b124 = rl_new_block("code 124"); + block_map[124] = b124; + rl_relooper_add_block(rl, block_map[124]); + void *b125 = rl_new_block("code 125"); + block_map[125] = b125; + rl_relooper_add_block(rl, block_map[125]); + void *b126 = rl_new_block("code 126"); + block_map[126] = b126; + rl_relooper_add_block(rl, block_map[126]); + void *b127 = rl_new_block("code 127"); + block_map[127] = b127; + rl_relooper_add_block(rl, block_map[127]); + void *b128 = rl_new_block("code 128"); + block_map[128] = b128; + rl_relooper_add_block(rl, block_map[128]); + void *b129 = rl_new_block("code 129"); + block_map[129] = b129; + rl_relooper_add_block(rl, block_map[129]); + void *b130 = rl_new_block("code 130"); + block_map[130] = b130; + rl_relooper_add_block(rl, block_map[130]); + void *b131 = rl_new_block("code 131"); + block_map[131] = b131; + rl_relooper_add_block(rl, block_map[131]); + void *b132 = rl_new_block("code 132"); + block_map[132] = b132; + rl_relooper_add_block(rl, block_map[132]); + void *b133 = rl_new_block("code 133"); + block_map[133] = b133; + rl_relooper_add_block(rl, block_map[133]); + void *b134 = rl_new_block("code 134"); + block_map[134] = b134; + rl_relooper_add_block(rl, block_map[134]); + void *b135 = rl_new_block("code 135"); + block_map[135] = b135; + rl_relooper_add_block(rl, block_map[135]); + void *b136 = rl_new_block("code 136"); + block_map[136] = b136; + rl_relooper_add_block(rl, block_map[136]); + void *b137 = rl_new_block("code 137"); + block_map[137] = b137; + rl_relooper_add_block(rl, block_map[137]); + void *b138 = rl_new_block("code 138"); + block_map[138] = b138; + rl_relooper_add_block(rl, block_map[138]); + void *b139 = rl_new_block("code 139"); + block_map[139] = b139; + rl_relooper_add_block(rl, block_map[139]); + void *b140 = rl_new_block("code 140"); + block_map[140] = b140; + rl_relooper_add_block(rl, block_map[140]); + void *b141 = rl_new_block("code 141"); + block_map[141] = b141; + rl_relooper_add_block(rl, block_map[141]); + void *b142 = rl_new_block("code 142"); + block_map[142] = b142; + rl_relooper_add_block(rl, block_map[142]); + void *b143 = rl_new_block("code 143"); + block_map[143] = b143; + rl_relooper_add_block(rl, block_map[143]); + void *b144 = rl_new_block("code 144"); + block_map[144] = b144; + rl_relooper_add_block(rl, block_map[144]); + void *b145 = rl_new_block("code 145"); + block_map[145] = b145; + rl_relooper_add_block(rl, block_map[145]); + void *b146 = rl_new_block("code 146"); + block_map[146] = b146; + rl_relooper_add_block(rl, block_map[146]); + void *b147 = rl_new_block("code 147"); + block_map[147] = b147; + rl_relooper_add_block(rl, block_map[147]); + void *b148 = rl_new_block("code 148"); + block_map[148] = b148; + rl_relooper_add_block(rl, block_map[148]); + void *b149 = rl_new_block("code 149"); + block_map[149] = b149; + rl_relooper_add_block(rl, block_map[149]); + void *b150 = rl_new_block("code 150"); + block_map[150] = b150; + rl_relooper_add_block(rl, block_map[150]); + void *b151 = rl_new_block("code 151"); + block_map[151] = b151; + rl_relooper_add_block(rl, block_map[151]); + void *b152 = rl_new_block("code 152"); + block_map[152] = b152; + rl_relooper_add_block(rl, block_map[152]); + void *b153 = rl_new_block("code 153"); + block_map[153] = b153; + rl_relooper_add_block(rl, block_map[153]); + void *b154 = rl_new_block("code 154"); + block_map[154] = b154; + rl_relooper_add_block(rl, block_map[154]); + void *b155 = rl_new_block("code 155"); + block_map[155] = b155; + rl_relooper_add_block(rl, block_map[155]); + void *b156 = rl_new_block("code 156"); + block_map[156] = b156; + rl_relooper_add_block(rl, block_map[156]); + void *b157 = rl_new_block("code 157"); + block_map[157] = b157; + rl_relooper_add_block(rl, block_map[157]); + void *b158 = rl_new_block("code 158"); + block_map[158] = b158; + rl_relooper_add_block(rl, block_map[158]); + void *b159 = rl_new_block("code 159"); + block_map[159] = b159; + rl_relooper_add_block(rl, block_map[159]); + void *b160 = rl_new_block("code 160"); + block_map[160] = b160; + rl_relooper_add_block(rl, block_map[160]); + void *b161 = rl_new_block("code 161"); + block_map[161] = b161; + rl_relooper_add_block(rl, block_map[161]); + void *b162 = rl_new_block("code 162"); + block_map[162] = b162; + rl_relooper_add_block(rl, block_map[162]); + void *b163 = rl_new_block("code 163"); + block_map[163] = b163; + rl_relooper_add_block(rl, block_map[163]); + void *b164 = rl_new_block("code 164"); + block_map[164] = b164; + rl_relooper_add_block(rl, block_map[164]); + void *b165 = rl_new_block("code 165"); + block_map[165] = b165; + rl_relooper_add_block(rl, block_map[165]); + void *b166 = rl_new_block("code 166"); + block_map[166] = b166; + rl_relooper_add_block(rl, block_map[166]); + void *b167 = rl_new_block("code 167"); + block_map[167] = b167; + rl_relooper_add_block(rl, block_map[167]); + void *b168 = rl_new_block("code 168"); + block_map[168] = b168; + rl_relooper_add_block(rl, block_map[168]); + void *b169 = rl_new_block("code 169"); + block_map[169] = b169; + rl_relooper_add_block(rl, block_map[169]); + void *b170 = rl_new_block("code 170"); + block_map[170] = b170; + rl_relooper_add_block(rl, block_map[170]); + void *b171 = rl_new_block("code 171"); + block_map[171] = b171; + rl_relooper_add_block(rl, block_map[171]); + void *b172 = rl_new_block("code 172"); + block_map[172] = b172; + rl_relooper_add_block(rl, block_map[172]); + void *b173 = rl_new_block("code 173"); + block_map[173] = b173; + rl_relooper_add_block(rl, block_map[173]); + void *b174 = rl_new_block("code 174"); + block_map[174] = b174; + rl_relooper_add_block(rl, block_map[174]); + void *b175 = rl_new_block("code 175"); + block_map[175] = b175; + rl_relooper_add_block(rl, block_map[175]); + void *b176 = rl_new_block("code 176"); + block_map[176] = b176; + rl_relooper_add_block(rl, block_map[176]); + void *b177 = rl_new_block("code 177"); + block_map[177] = b177; + rl_relooper_add_block(rl, block_map[177]); + void *b178 = rl_new_block("code 178"); + block_map[178] = b178; + rl_relooper_add_block(rl, block_map[178]); + void *b179 = rl_new_block("code 179"); + block_map[179] = b179; + rl_relooper_add_block(rl, block_map[179]); + void *b180 = rl_new_block("code 180"); + block_map[180] = b180; + rl_relooper_add_block(rl, block_map[180]); + void *b181 = rl_new_block("code 181"); + block_map[181] = b181; + rl_relooper_add_block(rl, block_map[181]); + void *b182 = rl_new_block("code 182"); + block_map[182] = b182; + rl_relooper_add_block(rl, block_map[182]); + void *b183 = rl_new_block("code 183"); + block_map[183] = b183; + rl_relooper_add_block(rl, block_map[183]); + rl_block_add_branch_to(block_map[0], block_map[2], "uint(i4) >= uint(i5)", NULL); + rl_block_add_branch_to(block_map[0], block_map[1], NULL, NULL); + rl_block_add_branch_to(block_map[1], block_map[3], NULL, NULL); + rl_block_add_branch_to(block_map[2], block_map[3], NULL, NULL); + rl_block_add_branch_to(block_map[3], block_map[15], "i2 == 0", NULL); + rl_block_add_branch_to(block_map[3], block_map[4], NULL, NULL); + rl_block_add_branch_to(block_map[4], block_map[5], NULL, NULL); + rl_block_add_branch_to(block_map[5], block_map[7], "uint(i6) >= uint(i7)", NULL); + rl_block_add_branch_to(block_map[5], block_map[6], NULL, NULL); + rl_block_add_branch_to(block_map[6], block_map[8], NULL, NULL); + rl_block_add_branch_to(block_map[7], block_map[8], NULL, NULL); + rl_block_add_branch_to(block_map[8], block_map[10], "uint(i6) >= uint(i7)", NULL); + rl_block_add_branch_to(block_map[8], block_map[9], NULL, NULL); + rl_block_add_branch_to(block_map[9], block_map[11], NULL, NULL); + rl_block_add_branch_to(block_map[10], block_map[11], NULL, NULL); + rl_block_add_branch_to(block_map[11], block_map[13], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[11], block_map[12], NULL, NULL); + rl_block_add_branch_to(block_map[12], block_map[14], NULL, NULL); + rl_block_add_branch_to(block_map[13], block_map[14], NULL, NULL); + rl_block_add_branch_to(block_map[14], block_map[5], "i2 != 0", NULL); + rl_block_add_branch_to(block_map[14], block_map[15], NULL, NULL); + rl_block_add_branch_to(block_map[15], block_map[17], "uint(i4) >= uint(i5)", NULL); + rl_block_add_branch_to(block_map[15], block_map[16], NULL, NULL); + rl_block_add_branch_to(block_map[16], block_map[18], NULL, NULL); + rl_block_add_branch_to(block_map[17], block_map[18], NULL, NULL); + rl_block_add_branch_to(block_map[18], block_map[102], "i2 == 0", NULL); + rl_block_add_branch_to(block_map[18], block_map[19], NULL, NULL); + rl_block_add_branch_to(block_map[19], block_map[20], NULL, NULL); + rl_block_add_branch_to(block_map[20], block_map[22], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[20], block_map[21], NULL, NULL); + rl_block_add_branch_to(block_map[21], block_map[23], NULL, NULL); + rl_block_add_branch_to(block_map[22], block_map[23], NULL, NULL); + rl_block_add_branch_to(block_map[23], block_map[25], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[23], block_map[24], NULL, NULL); + rl_block_add_branch_to(block_map[24], block_map[26], NULL, NULL); + rl_block_add_branch_to(block_map[25], block_map[26], NULL, NULL); + rl_block_add_branch_to(block_map[26], block_map[28], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[26], block_map[27], NULL, NULL); + rl_block_add_branch_to(block_map[27], block_map[29], NULL, NULL); + rl_block_add_branch_to(block_map[28], block_map[29], NULL, NULL); + rl_block_add_branch_to(block_map[29], block_map[31], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[29], block_map[30], NULL, NULL); + rl_block_add_branch_to(block_map[30], block_map[32], NULL, NULL); + rl_block_add_branch_to(block_map[31], block_map[32], NULL, NULL); + rl_block_add_branch_to(block_map[32], block_map[34], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[32], block_map[33], NULL, NULL); + rl_block_add_branch_to(block_map[33], block_map[35], NULL, NULL); + rl_block_add_branch_to(block_map[34], block_map[35], NULL, NULL); + rl_block_add_branch_to(block_map[35], block_map[37], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[35], block_map[36], NULL, NULL); + rl_block_add_branch_to(block_map[36], block_map[38], NULL, NULL); + rl_block_add_branch_to(block_map[37], block_map[38], NULL, NULL); + rl_block_add_branch_to(block_map[38], block_map[40], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[38], block_map[39], NULL, NULL); + rl_block_add_branch_to(block_map[39], block_map[41], NULL, NULL); + rl_block_add_branch_to(block_map[40], block_map[41], NULL, NULL); + rl_block_add_branch_to(block_map[41], block_map[43], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[41], block_map[42], NULL, NULL); + rl_block_add_branch_to(block_map[42], block_map[44], NULL, NULL); + rl_block_add_branch_to(block_map[43], block_map[44], NULL, NULL); + rl_block_add_branch_to(block_map[44], block_map[46], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[44], block_map[45], NULL, NULL); + rl_block_add_branch_to(block_map[45], block_map[47], NULL, NULL); + rl_block_add_branch_to(block_map[46], block_map[47], NULL, NULL); + rl_block_add_branch_to(block_map[47], block_map[49], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[47], block_map[48], NULL, NULL); + rl_block_add_branch_to(block_map[48], block_map[50], NULL, NULL); + rl_block_add_branch_to(block_map[49], block_map[50], NULL, NULL); + rl_block_add_branch_to(block_map[50], block_map[52], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[50], block_map[51], NULL, NULL); + rl_block_add_branch_to(block_map[51], block_map[53], NULL, NULL); + rl_block_add_branch_to(block_map[52], block_map[53], NULL, NULL); + rl_block_add_branch_to(block_map[53], block_map[55], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[53], block_map[54], NULL, NULL); + rl_block_add_branch_to(block_map[54], block_map[56], NULL, NULL); + rl_block_add_branch_to(block_map[55], block_map[56], NULL, NULL); + rl_block_add_branch_to(block_map[56], block_map[58], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[56], block_map[57], NULL, NULL); + rl_block_add_branch_to(block_map[57], block_map[59], NULL, NULL); + rl_block_add_branch_to(block_map[58], block_map[59], NULL, NULL); + rl_block_add_branch_to(block_map[59], block_map[61], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[59], block_map[60], NULL, NULL); + rl_block_add_branch_to(block_map[60], block_map[62], NULL, NULL); + rl_block_add_branch_to(block_map[61], block_map[62], NULL, NULL); + rl_block_add_branch_to(block_map[62], block_map[64], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[62], block_map[63], NULL, NULL); + rl_block_add_branch_to(block_map[63], block_map[65], NULL, NULL); + rl_block_add_branch_to(block_map[64], block_map[65], NULL, NULL); + rl_block_add_branch_to(block_map[65], block_map[67], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[65], block_map[66], NULL, NULL); + rl_block_add_branch_to(block_map[66], block_map[68], NULL, NULL); + rl_block_add_branch_to(block_map[67], block_map[68], NULL, NULL); + rl_block_add_branch_to(block_map[68], block_map[70], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[68], block_map[69], NULL, NULL); + rl_block_add_branch_to(block_map[69], block_map[71], NULL, NULL); + rl_block_add_branch_to(block_map[70], block_map[71], NULL, NULL); + rl_block_add_branch_to(block_map[71], block_map[73], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[71], block_map[72], NULL, NULL); + rl_block_add_branch_to(block_map[72], block_map[74], NULL, NULL); + rl_block_add_branch_to(block_map[73], block_map[74], NULL, NULL); + rl_block_add_branch_to(block_map[74], block_map[76], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[74], block_map[75], NULL, NULL); + rl_block_add_branch_to(block_map[75], block_map[77], NULL, NULL); + rl_block_add_branch_to(block_map[76], block_map[77], NULL, NULL); + rl_block_add_branch_to(block_map[77], block_map[79], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[77], block_map[78], NULL, NULL); + rl_block_add_branch_to(block_map[78], block_map[80], NULL, NULL); + rl_block_add_branch_to(block_map[79], block_map[80], NULL, NULL); + rl_block_add_branch_to(block_map[80], block_map[82], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[80], block_map[81], NULL, NULL); + rl_block_add_branch_to(block_map[81], block_map[83], NULL, NULL); + rl_block_add_branch_to(block_map[82], block_map[83], NULL, NULL); + rl_block_add_branch_to(block_map[83], block_map[85], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[83], block_map[84], NULL, NULL); + rl_block_add_branch_to(block_map[84], block_map[86], NULL, NULL); + rl_block_add_branch_to(block_map[85], block_map[86], NULL, NULL); + rl_block_add_branch_to(block_map[86], block_map[88], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[86], block_map[87], NULL, NULL); + rl_block_add_branch_to(block_map[87], block_map[89], NULL, NULL); + rl_block_add_branch_to(block_map[88], block_map[89], NULL, NULL); + rl_block_add_branch_to(block_map[89], block_map[91], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[89], block_map[90], NULL, NULL); + rl_block_add_branch_to(block_map[90], block_map[92], NULL, NULL); + rl_block_add_branch_to(block_map[91], block_map[92], NULL, NULL); + rl_block_add_branch_to(block_map[92], block_map[94], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[92], block_map[93], NULL, NULL); + rl_block_add_branch_to(block_map[93], block_map[95], NULL, NULL); + rl_block_add_branch_to(block_map[94], block_map[95], NULL, NULL); + rl_block_add_branch_to(block_map[95], block_map[97], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[95], block_map[96], NULL, NULL); + rl_block_add_branch_to(block_map[96], block_map[98], NULL, NULL); + rl_block_add_branch_to(block_map[97], block_map[98], NULL, NULL); + rl_block_add_branch_to(block_map[98], block_map[100], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[98], block_map[99], NULL, NULL); + rl_block_add_branch_to(block_map[99], block_map[101], NULL, NULL); + rl_block_add_branch_to(block_map[100], block_map[101], NULL, NULL); + rl_block_add_branch_to(block_map[101], block_map[20], "i2 != 0", NULL); + rl_block_add_branch_to(block_map[101], block_map[102], NULL, NULL); + rl_block_add_branch_to(block_map[102], block_map[104], "uint(i4) >= uint(i5)", NULL); + rl_block_add_branch_to(block_map[102], block_map[103], NULL, NULL); + rl_block_add_branch_to(block_map[103], block_map[105], NULL, NULL); + rl_block_add_branch_to(block_map[104], block_map[105], NULL, NULL); + rl_block_add_branch_to(block_map[105], block_map[168], "i2 == 0", NULL); + rl_block_add_branch_to(block_map[105], block_map[106], NULL, NULL); + rl_block_add_branch_to(block_map[106], block_map[107], NULL, NULL); + rl_block_add_branch_to(block_map[107], block_map[109], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[107], block_map[108], NULL, NULL); + rl_block_add_branch_to(block_map[108], block_map[110], NULL, NULL); + rl_block_add_branch_to(block_map[109], block_map[110], NULL, NULL); + rl_block_add_branch_to(block_map[110], block_map[112], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[110], block_map[111], NULL, NULL); + rl_block_add_branch_to(block_map[111], block_map[113], NULL, NULL); + rl_block_add_branch_to(block_map[112], block_map[113], NULL, NULL); + rl_block_add_branch_to(block_map[113], block_map[115], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[113], block_map[114], NULL, NULL); + rl_block_add_branch_to(block_map[114], block_map[116], NULL, NULL); + rl_block_add_branch_to(block_map[115], block_map[116], NULL, NULL); + rl_block_add_branch_to(block_map[116], block_map[118], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[116], block_map[117], NULL, NULL); + rl_block_add_branch_to(block_map[117], block_map[119], NULL, NULL); + rl_block_add_branch_to(block_map[118], block_map[119], NULL, NULL); + rl_block_add_branch_to(block_map[119], block_map[121], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[119], block_map[120], NULL, NULL); + rl_block_add_branch_to(block_map[120], block_map[122], NULL, NULL); + rl_block_add_branch_to(block_map[121], block_map[122], NULL, NULL); + rl_block_add_branch_to(block_map[122], block_map[124], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[122], block_map[123], NULL, NULL); + rl_block_add_branch_to(block_map[123], block_map[125], NULL, NULL); + rl_block_add_branch_to(block_map[124], block_map[125], NULL, NULL); + rl_block_add_branch_to(block_map[125], block_map[127], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[125], block_map[126], NULL, NULL); + rl_block_add_branch_to(block_map[126], block_map[128], NULL, NULL); + rl_block_add_branch_to(block_map[127], block_map[128], NULL, NULL); + rl_block_add_branch_to(block_map[128], block_map[130], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[128], block_map[129], NULL, NULL); + rl_block_add_branch_to(block_map[129], block_map[131], NULL, NULL); + rl_block_add_branch_to(block_map[130], block_map[131], NULL, NULL); + rl_block_add_branch_to(block_map[131], block_map[133], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[131], block_map[132], NULL, NULL); + rl_block_add_branch_to(block_map[132], block_map[134], NULL, NULL); + rl_block_add_branch_to(block_map[133], block_map[134], NULL, NULL); + rl_block_add_branch_to(block_map[134], block_map[136], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[134], block_map[135], NULL, NULL); + rl_block_add_branch_to(block_map[135], block_map[137], NULL, NULL); + rl_block_add_branch_to(block_map[136], block_map[137], NULL, NULL); + rl_block_add_branch_to(block_map[137], block_map[139], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[137], block_map[138], NULL, NULL); + rl_block_add_branch_to(block_map[138], block_map[140], NULL, NULL); + rl_block_add_branch_to(block_map[139], block_map[140], NULL, NULL); + rl_block_add_branch_to(block_map[140], block_map[142], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[140], block_map[141], NULL, NULL); + rl_block_add_branch_to(block_map[141], block_map[143], NULL, NULL); + rl_block_add_branch_to(block_map[142], block_map[143], NULL, NULL); + rl_block_add_branch_to(block_map[143], block_map[145], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[143], block_map[144], NULL, NULL); + rl_block_add_branch_to(block_map[144], block_map[146], NULL, NULL); + rl_block_add_branch_to(block_map[145], block_map[146], NULL, NULL); + rl_block_add_branch_to(block_map[146], block_map[148], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[146], block_map[147], NULL, NULL); + rl_block_add_branch_to(block_map[147], block_map[149], NULL, NULL); + rl_block_add_branch_to(block_map[148], block_map[149], NULL, NULL); + rl_block_add_branch_to(block_map[149], block_map[151], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[149], block_map[150], NULL, NULL); + rl_block_add_branch_to(block_map[150], block_map[152], NULL, NULL); + rl_block_add_branch_to(block_map[151], block_map[152], NULL, NULL); + rl_block_add_branch_to(block_map[152], block_map[154], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[152], block_map[153], NULL, NULL); + rl_block_add_branch_to(block_map[153], block_map[155], NULL, NULL); + rl_block_add_branch_to(block_map[154], block_map[155], NULL, NULL); + rl_block_add_branch_to(block_map[155], block_map[157], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[155], block_map[156], NULL, NULL); + rl_block_add_branch_to(block_map[156], block_map[158], NULL, NULL); + rl_block_add_branch_to(block_map[157], block_map[158], NULL, NULL); + rl_block_add_branch_to(block_map[158], block_map[160], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[158], block_map[159], NULL, NULL); + rl_block_add_branch_to(block_map[159], block_map[161], NULL, NULL); + rl_block_add_branch_to(block_map[160], block_map[161], NULL, NULL); + rl_block_add_branch_to(block_map[161], block_map[163], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[161], block_map[162], NULL, NULL); + rl_block_add_branch_to(block_map[162], block_map[164], NULL, NULL); + rl_block_add_branch_to(block_map[163], block_map[164], NULL, NULL); + rl_block_add_branch_to(block_map[164], block_map[166], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[164], block_map[165], NULL, NULL); + rl_block_add_branch_to(block_map[165], block_map[167], NULL, NULL); + rl_block_add_branch_to(block_map[166], block_map[167], NULL, NULL); + rl_block_add_branch_to(block_map[167], block_map[107], "i2 != 0", NULL); + rl_block_add_branch_to(block_map[167], block_map[168], NULL, NULL); + rl_block_add_branch_to(block_map[168], block_map[170], "uint(i4) >= uint(i5)", NULL); + rl_block_add_branch_to(block_map[168], block_map[169], NULL, NULL); + rl_block_add_branch_to(block_map[169], block_map[171], NULL, NULL); + rl_block_add_branch_to(block_map[170], block_map[171], NULL, NULL); + rl_block_add_branch_to(block_map[171], block_map[183], "i2 == 0", NULL); + rl_block_add_branch_to(block_map[171], block_map[172], NULL, NULL); + rl_block_add_branch_to(block_map[172], block_map[173], NULL, NULL); + rl_block_add_branch_to(block_map[173], block_map[175], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[173], block_map[174], NULL, NULL); + rl_block_add_branch_to(block_map[174], block_map[176], NULL, NULL); + rl_block_add_branch_to(block_map[175], block_map[176], NULL, NULL); + rl_block_add_branch_to(block_map[176], block_map[178], "uint(i5) >= uint(i6)", NULL); + rl_block_add_branch_to(block_map[176], block_map[177], NULL, NULL); + rl_block_add_branch_to(block_map[177], block_map[179], NULL, NULL); + rl_block_add_branch_to(block_map[178], block_map[179], NULL, NULL); + rl_block_add_branch_to(block_map[179], block_map[181], "uint(i4) >= uint(i5)", NULL); + rl_block_add_branch_to(block_map[179], block_map[180], NULL, NULL); + rl_block_add_branch_to(block_map[180], block_map[182], NULL, NULL); + rl_block_add_branch_to(block_map[181], block_map[182], NULL, NULL); + rl_block_add_branch_to(block_map[182], block_map[173], "i2 != 0", NULL); + rl_block_add_branch_to(block_map[182], block_map[183], NULL, NULL); + rl_relooper_calculate(rl, block_map[0]); + rl_relooper_render(rl); + rl_delete_relooper(rl); + puts(buffer); + return 0; +} + diff --git a/src/relooper/test_inf.txt b/src/relooper/test_inf.txt new file mode 100644 index 00000000..2edfc760 --- /dev/null +++ b/src/relooper/test_inf.txt @@ -0,0 +1,392 @@ +code 0 +if (uint(i4) >= uint(i5)) { + code 2 +} else { + code 1 +} +code 3 +L5: do { + if (!(i2 == 0)) { + code 4 + while(1) { + code 5 + if (uint(i6) >= uint(i7)) { + code 7 + } else { + code 6 + } + code 8 + if (uint(i6) >= uint(i7)) { + code 10 + } else { + code 9 + } + code 11 + if (uint(i5) >= uint(i6)) { + code 13 + } else { + code 12 + } + code 14 + if (!(i2 != 0)) { + break L5; + } + } + } +} while(0); +code 15 +if (uint(i4) >= uint(i5)) { + code 17 +} else { + code 16 +} +code 18 +L26: do { + if (!(i2 == 0)) { + code 19 + while(1) { + code 20 + if (uint(i5) >= uint(i6)) { + code 22 + } else { + code 21 + } + code 23 + if (uint(i5) >= uint(i6)) { + code 25 + } else { + code 24 + } + code 26 + if (uint(i5) >= uint(i6)) { + code 28 + } else { + code 27 + } + code 29 + if (uint(i5) >= uint(i6)) { + code 31 + } else { + code 30 + } + code 32 + if (uint(i5) >= uint(i6)) { + code 34 + } else { + code 33 + } + code 35 + if (uint(i5) >= uint(i6)) { + code 37 + } else { + code 36 + } + code 38 + if (uint(i5) >= uint(i6)) { + code 40 + } else { + code 39 + } + code 41 + if (uint(i5) >= uint(i6)) { + code 43 + } else { + code 42 + } + code 44 + if (uint(i5) >= uint(i6)) { + code 46 + } else { + code 45 + } + code 47 + if (uint(i5) >= uint(i6)) { + code 49 + } else { + code 48 + } + code 50 + if (uint(i5) >= uint(i6)) { + code 52 + } else { + code 51 + } + code 53 + if (uint(i5) >= uint(i6)) { + code 55 + } else { + code 54 + } + code 56 + if (uint(i5) >= uint(i6)) { + code 58 + } else { + code 57 + } + code 59 + if (uint(i5) >= uint(i6)) { + code 61 + } else { + code 60 + } + code 62 + if (uint(i5) >= uint(i6)) { + code 64 + } else { + code 63 + } + code 65 + if (uint(i5) >= uint(i6)) { + code 67 + } else { + code 66 + } + code 68 + if (uint(i5) >= uint(i6)) { + code 70 + } else { + code 69 + } + code 71 + if (uint(i5) >= uint(i6)) { + code 73 + } else { + code 72 + } + code 74 + if (uint(i5) >= uint(i6)) { + code 76 + } else { + code 75 + } + code 77 + if (uint(i5) >= uint(i6)) { + code 79 + } else { + code 78 + } + code 80 + if (uint(i5) >= uint(i6)) { + code 82 + } else { + code 81 + } + code 83 + if (uint(i5) >= uint(i6)) { + code 85 + } else { + code 84 + } + code 86 + if (uint(i5) >= uint(i6)) { + code 88 + } else { + code 87 + } + code 89 + if (uint(i5) >= uint(i6)) { + code 91 + } else { + code 90 + } + code 92 + if (uint(i5) >= uint(i6)) { + code 94 + } else { + code 93 + } + code 95 + if (uint(i5) >= uint(i6)) { + code 97 + } else { + code 96 + } + code 98 + if (uint(i5) >= uint(i6)) { + code 100 + } else { + code 99 + } + code 101 + if (!(i2 != 0)) { + break L26; + } + } + } +} while(0); +code 102 +if (uint(i4) >= uint(i5)) { + code 104 +} else { + code 103 +} +code 105 +L143: do { + if (!(i2 == 0)) { + code 106 + while(1) { + code 107 + if (uint(i5) >= uint(i6)) { + code 109 + } else { + code 108 + } + code 110 + if (uint(i5) >= uint(i6)) { + code 112 + } else { + code 111 + } + code 113 + if (uint(i5) >= uint(i6)) { + code 115 + } else { + code 114 + } + code 116 + if (uint(i5) >= uint(i6)) { + code 118 + } else { + code 117 + } + code 119 + if (uint(i5) >= uint(i6)) { + code 121 + } else { + code 120 + } + code 122 + if (uint(i5) >= uint(i6)) { + code 124 + } else { + code 123 + } + code 125 + if (uint(i5) >= uint(i6)) { + code 127 + } else { + code 126 + } + code 128 + if (uint(i5) >= uint(i6)) { + code 130 + } else { + code 129 + } + code 131 + if (uint(i5) >= uint(i6)) { + code 133 + } else { + code 132 + } + code 134 + if (uint(i5) >= uint(i6)) { + code 136 + } else { + code 135 + } + code 137 + if (uint(i5) >= uint(i6)) { + code 139 + } else { + code 138 + } + code 140 + if (uint(i5) >= uint(i6)) { + code 142 + } else { + code 141 + } + code 143 + if (uint(i5) >= uint(i6)) { + code 145 + } else { + code 144 + } + code 146 + if (uint(i5) >= uint(i6)) { + code 148 + } else { + code 147 + } + code 149 + if (uint(i5) >= uint(i6)) { + code 151 + } else { + code 150 + } + code 152 + if (uint(i5) >= uint(i6)) { + code 154 + } else { + code 153 + } + code 155 + if (uint(i5) >= uint(i6)) { + code 157 + } else { + code 156 + } + code 158 + if (uint(i5) >= uint(i6)) { + code 160 + } else { + code 159 + } + code 161 + if (uint(i5) >= uint(i6)) { + code 163 + } else { + code 162 + } + code 164 + if (uint(i5) >= uint(i6)) { + code 166 + } else { + code 165 + } + code 167 + if (!(i2 != 0)) { + break L143; + } + } + } +} while(0); +code 168 +if (uint(i4) >= uint(i5)) { + code 170 +} else { + code 169 +} +code 171 +if (i2 == 0) { + code 183 +} else { + code 172 + while(1) { + code 173 + if (uint(i5) >= uint(i6)) { + code 175 + } else { + code 174 + } + code 176 + if (uint(i5) >= uint(i6)) { + code 178 + } else { + code 177 + } + code 179 + if (uint(i4) >= uint(i5)) { + code 181 + } else { + code 180 + } + code 182 + if (!(i2 != 0)) { + break; + } + } + code 183 +} + diff --git a/src/relooper/testit.sh b/src/relooper/testit.sh new file mode 100755 index 00000000..28413c0d --- /dev/null +++ b/src/relooper/testit.sh @@ -0,0 +1,60 @@ +echo "test" +./test &> test.out +diff -U 5 test.txt test.out + +echo "test 2" +./test2 &> test2.out +diff -U 5 test2.txt test2.out + +echo "test 3" +./test3 &> test3.out +diff -U 5 test3.txt test3.out + +echo "test debug" +./test_debug &> test_debug.out +diff -U 5 test_debug.txt test_debug.out + +echo "test dead" +./test_dead &> test_dead.out +diff -U 5 test_dead.txt test_dead.out + +echo "test 4" +./test4 &> test4.out +diff -U 5 test4.txt test4.out + +echo "test 5" +./test5 &> test5.out +diff -U 5 test5.txt test5.out + +echo "test 6" +./test6 &> test6.out +diff -U 5 test6.txt test6.out + +echo "test inf" +./test_inf &> test_inf.out +diff -U 5 test_inf.txt test_inf.out + +echo "test fuzz1" +./test_fuzz1 &> test_fuzz1.out +diff -U 5 test_fuzz1.txt test_fuzz1.out + +echo "test fuzz2" +./test_fuzz2 &> test_fuzz2.out +diff -U 5 test_fuzz2.txt test_fuzz2.out + +echo "test fuzz3" +./test_fuzz3 &> test_fuzz3.out +diff -U 5 test_fuzz3.txt test_fuzz3.out + +echo "test fuzz4" +./test_fuzz4 &> test_fuzz4.out +diff -U 5 test_fuzz4.txt test_fuzz4.out + +echo "test fuzz5" +./test_fuzz5 &> test_fuzz5.out +diff -U 5 test_fuzz5.txt test_fuzz5.out + +echo "test fuzz6" +./test_fuzz6 &> test_fuzz6.out +diff -U 5 test_fuzz6.txt test_fuzz6.out + diff --git a/src/relooper/updateit.sh b/src/relooper/updateit.sh new file mode 100755 index 00000000..91ccd3ab --- /dev/null +++ b/src/relooper/updateit.sh @@ -0,0 +1,16 @@ +./test &> test.txt +./test2 &> test2.txt +./test3 &> test3.txt +./test_debug &> test_debug.txt +./test_dead &> test_dead.txt +./test4 &> test4.txt +./test5 &> test5.txt +./test6 &> test6.txt +./test_inf &> test_inf.txt +./test_fuzz1 &> test_fuzz1.txt +./test_fuzz2 &> test_fuzz2.txt +./test_fuzz3 &> test_fuzz3.txt +./test_fuzz4 &> test_fuzz4.txt +./test_fuzz5 &> test_fuzz5.txt +./test_fuzz6 &> test_fuzz6.txt + -- cgit v1.2.3-18-g5258