aboutsummaryrefslogtreecommitdiff
path: root/src/relooper
diff options
context:
space:
mode:
Diffstat (limited to 'src/relooper')
-rw-r--r--src/relooper/Relooper.cpp38
-rw-r--r--src/relooper/Relooper.h20
-rw-r--r--src/relooper/fuzzer.py6
-rw-r--r--src/relooper/test.cpp28
-rw-r--r--src/relooper/test.txt44
5 files changed, 123 insertions, 13 deletions
diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp
index d2a48f63..fc7b3ea7 100644
--- a/src/relooper/Relooper.cpp
+++ b/src/relooper/Relooper.cpp
@@ -142,6 +142,7 @@ void Block::Render(bool InLoop) {
if (!ProcessedBranchesOut.size()) return;
bool SetLabel = true; // in some cases it is clear we can avoid setting label, see later
+ bool ForceSetLabel = Shape::IsEmulated(Parent);
// A setting of the label variable (label = x) is necessary if it can
// cause an impact. The main case is where we set label to x, then elsewhere
@@ -210,7 +211,7 @@ void Block::Render(bool InLoop) {
Target = DefaultTarget;
Details = ProcessedBranchesOut[DefaultTarget];
}
- bool SetCurrLabel = SetLabel && Target->IsCheckedMultipleEntry;
+ bool SetCurrLabel = (SetLabel && Target->IsCheckedMultipleEntry) || ForceSetLabel;
bool HasFusedContent = Fused && contains(Fused->InnerMap, Target);
bool HasContent = SetCurrLabel || Details->Type != Branch::Direct || HasFusedContent || Details->Code;
if (iter != ProcessedBranchesOut.end()) {
@@ -330,16 +331,19 @@ void LoopShape::Render(bool InLoop) {
if (Next) Next->Render(InLoop);
};
-/*
// EmulatedShape
void EmulatedShape::Render(bool InLoop) {
+ PrintIndented("label = %d;\n", Entry->Id);
+ if (Labeled) {
+ PrintIndented("L%d: ", Id);
+ }
PrintIndented("while(1) {\n");
Indenter::Indent();
- PrintIndented("switch(label) {\n");
+ PrintIndented("switch(label|0) {\n");
Indenter::Indent();
- for (int i = 0; i < Blocks.size(); i++) {
- Block *Curr = Blocks[i];
+ for (BlockSet::iterator iter = Blocks.begin(); iter != Blocks.end(); iter++) {
+ Block *Curr = *iter;
PrintIndented("case %d: {\n", Curr->Id);
Indenter::Indent();
Curr->Render(InLoop);
@@ -353,11 +357,10 @@ void EmulatedShape::Render(bool InLoop) {
PrintIndented("}\n");
if (Next) Next->Render(InLoop);
};
-*/
// Relooper
-Relooper::Relooper() : Root(NULL) {
+Relooper::Relooper() : Root(NULL), Emulate(false) {
}
Relooper::~Relooper() {
@@ -461,7 +464,7 @@ void Relooper::Calculate(Block *Entry) {
}
}
- Pre.SplitDeadEnds();
+ if (!Emulate) Pre.SplitDeadEnds();
// Recursively process the graph
@@ -526,6 +529,21 @@ void Relooper::Calculate(Block *Entry) {
return Simple;
}
+ Shape *MakeEmulated(BlockSet &Blocks, Block *Entry, BlockSet &NextEntries) {
+ PrintDebug("creating emulated block with entry #%d and everything it can reach, %d blocks\n", Entry->Id, Blocks.size());
+ EmulatedShape *Emulated = new EmulatedShape;
+ Notice(Emulated);
+ Emulated->Entry = Entry;
+ for (BlockSet::iterator iter = Blocks.begin(); iter != Blocks.end(); iter++) {
+ Block *Curr = *iter;
+ Emulated->Blocks.insert(Curr);
+ Curr->Parent = Emulated;
+ Solipsize(Curr, Branch::Continue, Emulated, Blocks);
+ }
+ Blocks.clear();
+ return Emulated;
+ }
+
Shape *MakeLoop(BlockSet &Blocks, BlockSet& Entries, BlockSet &NextEntries) {
// Find the inner blocks in this loop. Proceed backwards from the entries until
// you reach a seen block, collecting as you go.
@@ -837,6 +855,9 @@ void Relooper::Calculate(Block *Entry) {
if (Entries->size() == 0) return Ret;
if (Entries->size() == 1) {
Block *Curr = *(Entries->begin());
+ if (Parent->Emulate) {
+ Make(MakeEmulated(Blocks, Curr, *NextEntries));
+ }
if (Curr->BranchesIn.size() == 0) {
// One entry, no looping ==> Simple
Make(MakeSimple(Blocks, Curr, *NextEntries));
@@ -844,6 +865,7 @@ void Relooper::Calculate(Block *Entry) {
// One entry, looping ==> Loop
Make(MakeLoop(Blocks, *Entries, *NextEntries));
}
+
// More than one entry, try to eliminate through a Multiple groups of
// independent blocks from an entry/ies. It is important to remove through
// multiples as opposed to looping since the former is more performant.
diff --git a/src/relooper/Relooper.h b/src/relooper/Relooper.h
index f3dedf8c..e78d18e7 100644
--- a/src/relooper/Relooper.h
+++ b/src/relooper/Relooper.h
@@ -96,6 +96,7 @@ class SimpleShape;
class LabeledShape;
class MultipleShape;
class LoopShape;
+class EmulatedShape;
struct Shape {
int Id; // A unique identifier. Used to identify loops, labels are Lx where x is the Id.
@@ -105,7 +106,8 @@ struct Shape {
enum ShapeType {
Simple,
Multiple,
- Loop
+ Loop,
+ Emulated
};
ShapeType Type;
@@ -118,6 +120,7 @@ struct Shape {
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; }
+ static EmulatedShape *IsEmulated(Shape *It) { return It && It->Type == Emulated ? (EmulatedShape*)It : NULL; }
// INTERNAL
static int IdCounter;
@@ -162,12 +165,15 @@ struct LoopShape : public LabeledShape {
void Render(bool InLoop);
};
-/*
-struct EmulatedShape : public Shape {
- std::deque<Block*> Blocks;
+// TODO EmulatedShape is only partially functional. Currently it can be used for the
+// entire set of blocks being relooped, but not subsets.
+struct EmulatedShape : public LabeledShape {
+ Block *Entry;
+ BlockSet Blocks;
+
+ EmulatedShape() : LabeledShape(Emulated) { Labeled = true; }
void Render(bool InLoop);
};
-*/
// Implements the relooper algorithm for a function's blocks.
//
@@ -184,6 +190,7 @@ struct Relooper {
std::deque<Block*> Blocks;
std::deque<Shape*> Shapes;
Shape *Root;
+ bool Emulate;
Relooper();
~Relooper();
@@ -204,6 +211,9 @@ struct Relooper {
// Sets asm.js mode on or off (default is off)
static void SetAsmJSMode(int On);
+
+ // Sets whether we must emulate everything with switch-loop code
+ void SetEmulate(int E) { Emulate = E; }
};
typedef std::map<Block*, BlockSet> BlockBlockSetMap;
diff --git a/src/relooper/fuzzer.py b/src/relooper/fuzzer.py
index 50846d10..fa47583e 100644
--- a/src/relooper/fuzzer.py
+++ b/src/relooper/fuzzer.py
@@ -87,6 +87,12 @@ int main() {
Relooper r;
'''
+ if random.random() < 0.1:
+ print 'emulate'
+ fast += '''
+ r.SetEmulate(true);
+'''
+
for i in range(num):
fast += ''' r.AddBlock(b%d);
''' % i
diff --git a/src/relooper/test.cpp b/src/relooper/test.cpp
index fbd9c7aa..773f6ee4 100644
--- a/src/relooper/test.cpp
+++ b/src/relooper/test.cpp
@@ -258,5 +258,33 @@ int main() {
puts(buffer);
}
+
+ if (1) {
+ Relooper::SetOutputBuffer(buffer, sizeof(buffer));
+
+ printf("\n\n-- If pattern, emulated --\n\n", "the_var");
+
+ Block *b_a = new Block("// block A\n", NULL);
+ Block *b_b = new Block("// block B\n", "b_check()");
+ Block *b_c = new Block("// block C\n", NULL);
+
+ b_a->AddBranchTo(b_b, "check == 10", "atob();");
+ b_a->AddBranchTo(b_c, NULL, "atoc();");
+
+ b_b->AddBranchTo(b_c, "case 17:", "btoc();");
+ b_b->AddBranchTo(b_a, NULL, NULL);
+
+ Relooper r;
+ r.SetEmulate(true);
+ r.AddBlock(b_a);
+ r.AddBlock(b_b);
+ r.AddBlock(b_c);
+
+ r.Calculate(b_a);
+ printf("\n\n", "the_var");
+ r.Render();
+
+ puts(buffer);
+ }
}
diff --git a/src/relooper/test.txt b/src/relooper/test.txt
index 2c530567..9b537fd9 100644
--- a/src/relooper/test.txt
+++ b/src/relooper/test.txt
@@ -270,3 +270,47 @@ L46: do {
} while(0);
// block C
+
+
+-- If pattern, emulated --
+
+
+
+L50: while(1) {
+ switch(label) {
+ case 40: {
+ // block A
+ if (check == 10) {
+ atob();
+ label = 41;
+ continue L50;
+ } else {
+ atoc();
+ label = 42;
+ continue L50;
+ }
+ break;
+ }
+ case 41: {
+ // block B
+ switch (b_check()) {
+ case 17: {
+ btoc();
+ label = 42;
+ continue L50;
+ break;
+ }
+ default: {
+ label = 40;
+ continue L50;
+ }
+ }
+ break;
+ }
+ case 42: {
+ // block C
+ break;
+ }
+ }
+}
+
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-21 19:31:45 +0000