aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/relooper/Relooper.cpp43
-rw-r--r--src/relooper/test.cpp7
-rw-r--r--src/relooper/test.txt32
-rw-r--r--src/relooper/test_fuzz1.txt43
-rw-r--r--src/relooper/test_fuzz2.txt9
-rw-r--r--src/relooper/test_fuzz4.txt19
-rw-r--r--src/relooper/test_fuzz6.txt53
-rw-r--r--src/relooper/test_inf.txt51
8 files changed, 146 insertions, 111 deletions
diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp
index f16055c0..933fda96 100644
--- a/src/relooper/Relooper.cpp
+++ b/src/relooper/Relooper.cpp
@@ -750,6 +750,49 @@ void Relooper::Calculate(Block *Entry) {
}
}
+ // As an optimization, if we have 2 independent groups, and one is a small dead end, we can handle only that dead end.
+ // The other then becomes a Next - without nesting in the code and recursion in the analysis.
+ // TODO: if the larger is the only dead end, handle that too
+ // TODO: handle >2 groups
+ // TODO: handle not just dead ends, but also that do not branch to the NextEntries. However, must be careful
+ // there since we create a Next, and that Next can prevent eliminating a break (since we no longer
+ // naturally reach the same place), which may necessitate a one-time loop, which makes the unnesting
+ // pointless.
+ if (IndependentGroups.size() == 2) {
+ // Find the smaller one
+ BlockBlockSetMap::iterator iter = IndependentGroups.begin();
+ Block *SmallEntry = iter->first;
+ int SmallSize = iter->second.size();
+ iter++;
+ Block *LargeEntry = iter->first;
+ int LargeSize = iter->second.size();
+ if (SmallSize != LargeSize) { // ignore the case where they are identical - keep things symmetrical there
+ if (SmallSize > LargeSize) {
+ Block *Temp = SmallEntry;
+ SmallEntry = LargeEntry;
+ LargeEntry = Temp; // Note: we did not flip the Sizes too, they are now invalid. TODO: use the smaller size as a limit?
+ }
+ // Check if dead end
+ bool DeadEnd = true;
+ BlockSet &SmallGroup = IndependentGroups[SmallEntry];
+ for (BlockSet::iterator iter = SmallGroup.begin(); iter != SmallGroup.end(); iter++) {
+ Block *Curr = *iter;
+ for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) {
+ Block *Target = iter->first;
+ if (SmallGroup.find(Target) == SmallGroup.end()) {
+ DeadEnd = false;
+ break;
+ }
+ }
+ if (!DeadEnd) break;
+ }
+ if (DeadEnd) {
+ PrintDebug("Removing nesting by not handling large group because small group is dead end\n");
+ IndependentGroups.erase(LargeEntry);
+ }
+ }
+ }
+
PrintDebug("Handleable independent groups: %d\n", IndependentGroups.size());
if (IndependentGroups.size() > 0) {
diff --git a/src/relooper/test.cpp b/src/relooper/test.cpp
index 0d029216..4275941b 100644
--- a/src/relooper/test.cpp
+++ b/src/relooper/test.cpp
@@ -160,7 +160,7 @@ int main() {
puts(buffer);
}
-/*
+
if (1) {
Relooper::SetOutputBuffer(buffer, sizeof(buffer));
@@ -168,11 +168,11 @@ int main() {
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_c = new Block("return C;\n");
Block *b_d = new Block("// block D\n");
b_a->AddBranchTo(b_b, "check == 10");
- b_a->AddBranchTo(b_c, NULL);
+ b_a->AddBranchTo(b_c, NULL); // c is a dead end
b_b->AddBranchTo(b_d, NULL);
@@ -190,6 +190,5 @@ int main() {
puts(buffer);
}
-*/
}
diff --git a/src/relooper/test.txt b/src/relooper/test.txt
index ff4ada24..12d0ef39 100644
--- a/src/relooper/test.txt
+++ b/src/relooper/test.txt
@@ -59,24 +59,21 @@ while(1) {
}
// 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;
+if (label == 18) {
// code 7
}
-else if (label == 18) {
- // code 7
+// code 4
+if ($10) {
+ // code 5
}
+// code 6
+var $x_1 = $13;
+// code 7
@@ -97,3 +94,18 @@ if (chak()) {
// block D
}
+
+
+-- Unbalanced with a dead end --
+
+
+
+// block A
+if (!(check == 10)) {
+ return C;
+}
+while(1) {
+ // block B
+ // block D
+}
+
diff --git a/src/relooper/test_fuzz1.txt b/src/relooper/test_fuzz1.txt
index 63bbee0c..5122257e 100644
--- a/src/relooper/test_fuzz1.txt
+++ b/src/relooper/test_fuzz1.txt
@@ -8,37 +8,28 @@ do {
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) {
+ if (label == 3) {
label = 0;
print(2); state = check();
- label = 2;
- continue;
+ }
+ print(1); state = check();
+ while(1) {
+ print(3); state = check();
+ if (!(state == 8)) {
+ continue L5;
+ }
+ print(8); state = check();
+ if (!(state == 4)) {
+ label = 3;
+ continue L5;
+ }
+ print(4); state = check();
+ if (!(state == 3)) {
+ continue L5;
+ }
}
}
diff --git a/src/relooper/test_fuzz2.txt b/src/relooper/test_fuzz2.txt
index c48c6b6c..572e819d 100644
--- a/src/relooper/test_fuzz2.txt
+++ b/src/relooper/test_fuzz2.txt
@@ -5,10 +5,9 @@ if (state == 1) {
while(1) {
print(1); state = check();
}
-} else {
- while(1) {
- print(3); state = check();
- print(2); state = check();
- }
+}
+while(1) {
+ print(3); state = check();
+ print(2); state = check();
}
diff --git a/src/relooper/test_fuzz4.txt b/src/relooper/test_fuzz4.txt
index 5bb219f4..05a70582 100644
--- a/src/relooper/test_fuzz4.txt
+++ b/src/relooper/test_fuzz4.txt
@@ -5,16 +5,15 @@ 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();
+}
+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_fuzz6.txt b/src/relooper/test_fuzz6.txt
index af188ab1..bd45e8fd 100644
--- a/src/relooper/test_fuzz6.txt
+++ b/src/relooper/test_fuzz6.txt
@@ -40,39 +40,14 @@ while(1) {
print(16); state = check();// ................................................................................................................................................................................................................................................................................................................................................................
print(57); state = check();// ...........................................................................................................................................................................................................................................................................................................................
print(39); state = check();// ................
- if (state % 3 == 0) {
- label = 73;
- } else if (state % 3 == 1) {
+ if (state % 3 == 1) {
label = 74;
- } else {
+ } else if (!(state % 3 == 0)) {
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) {
+ if (label == 74) {
label = 0;
print(73); state = check();// .
if (state % 3 == 1) {
@@ -87,9 +62,27 @@ while(1) {
print(77); state = check();// ...........................................................................................................................................................................................................................................................................................
print(76); state = check();// ..............................................................................................................................................................................................................................................................................................................................................................................................................................
print(22); state = check();// .........................................................................................................
- label = 73;
- continue;
}
+ 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;
}
print(62); state = check();// .......................................................................................
}
diff --git a/src/relooper/test_inf.txt b/src/relooper/test_inf.txt
index 2edfc760..379d2083 100644
--- a/src/relooper/test_inf.txt
+++ b/src/relooper/test_inf.txt
@@ -361,32 +361,31 @@ if (uint(i4) >= uint(i5)) {
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 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
}
+code 183
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-24 13:15:00 +0000