remove break labels more aggresively, with a refined natural flow analysis
diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp
index 1939831..8a6e18b 100644
--- a/src/relooper/Relooper.cpp
+++ b/src/relooper/Relooper.cpp
@@ -70,7 +70,7 @@
// Branch
-Branch::Branch(const char *ConditionInit, const char *CodeInit) : Ancestor(NULL), Labeled(false) {
+Branch::Branch(const char *ConditionInit, const char *CodeInit) : Ancestor(NULL), Labeled(true) {
Condition = ConditionInit ? strdup(ConditionInit) : NULL;
Code = CodeInit ? strdup(CodeInit) : NULL;
}
@@ -951,10 +951,28 @@
});
}
+ void FindNaturals(Shape *Root, Shape *Otherwise=NULL) {
+ if (Root->Next) {
+ Root->Natural = Root->Next;
+ FindNaturals(Root->Next, Otherwise);
+ } else {
+ Root->Natural = Otherwise;
+ }
+
+ SHAPE_SWITCH(Root, {
+ }, {
+ for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
+ FindNaturals(iter->second, Root->Natural);
+ }
+ }, {
+ FindNaturals(Loop->Inner, Loop->Inner);
+ });
+ }
+
// Remove unneeded breaks and continues.
// A flow operation is trivially unneeded if the shape we naturally get to by normal code
// execution is the same as the flow forces us to.
- void RemoveUnneededFlows(Shape *Root, Shape *Natural=NULL) {
+ void RemoveUnneededFlows(Shape *Root, Shape *Natural=NULL, LoopShape *LastLoop=NULL) {
BlockSet NaturalBlocks;
FollowNaturalFlow(Natural, NaturalBlocks);
Shape *Next = Root;
@@ -976,16 +994,22 @@
if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) {
Multiple->NeedLoop--;
}
+ } else if (Details->Type == Branch::Break && LastLoop && LastLoop->Natural == Details->Ancestor->Natural) {
+ // it is important to simplify breaks, as simpler breaks enable other optimizations
+ Details->Labeled = false;
+ if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) {
+ Multiple->NeedLoop--;
+ }
}
}
}
}, {
for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
- RemoveUnneededFlows(iter->second, Multiple->Next);
+ RemoveUnneededFlows(iter->second, Multiple->Next, Multiple->NeedLoop ? NULL : LastLoop);
}
Next = Multiple->Next;
}, {
- RemoveUnneededFlows(Loop->Inner, Loop->Inner);
+ RemoveUnneededFlows(Loop->Inner, Loop->Inner, Loop);
Next = Loop->Next;
});
}
@@ -1016,7 +1040,7 @@
Branch *Details = iter->second;
if (Details->Type != Branch::Direct) {
assert(LoopStack.size() > 0);
- if (Details->Ancestor != LoopStack.top()) {
+ if (Details->Ancestor != LoopStack.top() && Details->Labeled) {
LabeledShape *Labeled = Shape::IsLabeled(Details->Ancestor);
Labeled->Labeled = true;
Details->Labeled = true;
@@ -1054,6 +1078,7 @@
}
void Process(Shape *Root) {
+ FindNaturals(Root);
RemoveUnneededFlows(Root);
FindLabeledLoops(Root);
}
@@ -1101,6 +1126,10 @@
void Debugging::Dump(Shape *S, const char *prefix) {
if (prefix) printf("%s ", prefix);
+ if (!S) {
+ printf(" (null)\n");
+ return;
+ }
printf(" %d ", S->Id);
SHAPE_SWITCH(S, {
printf("<< Simple with block %d\n", Simple->Inner->Id);
diff --git a/src/relooper/Relooper.h b/src/relooper/Relooper.h
index 34b6db0..fe56a13 100644
--- a/src/relooper/Relooper.h
+++ b/src/relooper/Relooper.h
@@ -101,6 +101,7 @@
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
+ Shape *Natural; // The shape that control flow gets to naturally (if there is Next, then this is Next)
enum ShapeType {
Simple,
diff --git a/src/relooper/test.cpp b/src/relooper/test.cpp
index 7da990b..b2d500d 100644
--- a/src/relooper/test.cpp
+++ b/src/relooper/test.cpp
@@ -231,5 +231,32 @@
puts(buffer);
}
+
+ if (1) {
+ Relooper::SetOutputBuffer(buffer, sizeof(buffer));
+
+ printf("\n\n-- conditional loop --\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, "shouldLoop()");
+ b_a->AddBranchTo(b_c, NULL);
+
+ b_b->AddBranchTo(b_b, "moarLoop()");
+ 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);
+ }
}
diff --git a/src/relooper/test.txt b/src/relooper/test.txt
index d657c6a..b353559 100644
--- a/src/relooper/test.txt
+++ b/src/relooper/test.txt
@@ -136,3 +136,20 @@
// block F
}
+
+
+-- conditional loop --
+
+
+
+// block A
+if (shouldLoop()) {
+ while(1) {
+ // block B
+ if (!(moarLoop())) {
+ break;
+ }
+ }
+}
+// block C
+
diff --git a/src/relooper/test3.txt b/src/relooper/test3.txt
index 696542e..6049ee4 100644
--- a/src/relooper/test3.txt
+++ b/src/relooper/test3.txt
@@ -9,7 +9,7 @@
}
} while(0);
LBB3
-L5: do {
+do {
if (LBB3 -> LBB4) {
LBB4
if (!(LBB4 -> LBB5)) {
@@ -18,7 +18,7 @@
while(1) {
LBB5
if (LBB5 -> LBB6) {
- break L5;
+ break;
}
}
}
diff --git a/src/relooper/test_inf.txt b/src/relooper/test_inf.txt
index 379d208..1dff59b 100644
--- a/src/relooper/test_inf.txt
+++ b/src/relooper/test_inf.txt
@@ -5,35 +5,33 @@
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;
- }
+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;
}
}
-} while(0);
+}
code 15
if (uint(i4) >= uint(i5)) {
code 17
@@ -41,179 +39,177 @@
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;
- }
+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;
}
}
-} while(0);
+}
code 102
if (uint(i4) >= uint(i5)) {
code 104
@@ -221,137 +217,135 @@
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;
- }
+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;
}
}
-} while(0);
+}
code 168
if (uint(i4) >= uint(i5)) {
code 170
diff --git a/tools/shared.py b/tools/shared.py
index 4225be2..8a172d9 100644
--- a/tools/shared.py
+++ b/tools/shared.py
@@ -295,7 +295,7 @@
# we re-check sanity when the settings are changed)
# We also re-check sanity and clear the cache when the version changes
-EMSCRIPTEN_VERSION = '1.4.8'
+EMSCRIPTEN_VERSION = '1.4.9'
def generate_sanity():
return EMSCRIPTEN_VERSION + '|' + get_llvm_target()
