aboutsummaryrefslogtreecommitdiff
path: root/src/relooper
diff options
context:
space:
mode:
Diffstat (limited to 'src/relooper')
-rw-r--r--src/relooper/Relooper.cpp95
-rw-r--r--src/relooper/Relooper.h1
-rw-r--r--src/relooper/test.cpp27
-rw-r--r--src/relooper/test.txt17
-rw-r--r--src/relooper/test3.txt4
-rw-r--r--src/relooper/test_inf.txt648
6 files changed, 454 insertions, 338 deletions
diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp
index 8c72b0a6..8a6e18b8 100644
--- a/src/relooper/Relooper.cpp
+++ b/src/relooper/Relooper.cpp
@@ -70,7 +70,7 @@ int Indenter::CurrIndent = 0;
// 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;
}
@@ -522,14 +522,60 @@ void Relooper::Calculate(Block *Entry) {
}
}
+#if 0
+ // We can avoid multiple next entries by hoisting them into the loop.
+ if (NextEntries.size() > 1) {
+ BlockBlockSetMap IndependentGroups;
+ FindIndependentGroups(NextEntries, IndependentGroups, &InnerBlocks);
+
+ while (IndependentGroups.size() > 0 && NextEntries.size() > 1) {
+ Block *Min = NULL;
+ int MinSize = 0;
+ for (BlockBlockSetMap::iterator iter = IndependentGroups.begin(); iter != IndependentGroups.end(); iter++) {
+ Block *Entry = iter->first;
+ BlockSet &Blocks = iter->second;
+ if (!Min || Blocks.size() < MinSize) { // TODO: code size, not # of blocks
+ Min = Entry;
+ MinSize = Blocks.size();
+ }
+ }
+ // check how many new entries this would cause
+ BlockSet &Hoisted = IndependentGroups[Min];
+ bool abort = false;
+ for (BlockSet::iterator iter = Hoisted.begin(); iter != Hoisted.end() && !abort; iter++) {
+ Block *Curr = *iter;
+ for (BlockBranchMap::iterator iter = Curr->BranchesOut.begin(); iter != Curr->BranchesOut.end(); iter++) {
+ Block *Target = iter->first;
+ if (Hoisted.find(Target) == Hoisted.end() && NextEntries.find(Target) == NextEntries.end()) {
+ // abort this hoisting
+ abort = true;
+ break;
+ }
+ }
+ }
+ if (abort) {
+ IndependentGroups.erase(Min);
+ continue;
+ }
+ // hoist this entry
+ PrintDebug("hoisting %d into loop\n", Min->Id);
+ NextEntries.erase(Min);
+ for (BlockSet::iterator iter = Hoisted.begin(); iter != Hoisted.end(); iter++) {
+ Block *Curr = *iter;
+ InnerBlocks.insert(Curr);
+ Blocks.erase(Curr);
+ }
+ IndependentGroups.erase(Min);
+ }
+ }
+#endif
+
PrintDebug("creating loop block:\n");
DebugDump(InnerBlocks, " inner blocks:");
DebugDump(Entries, " inner entries:");
DebugDump(Blocks, " outer blocks:");
DebugDump(NextEntries, " outer entries:");
- // TODO: Optionally hoist additional blocks into the loop
-
LoopShape *Loop = new LoopShape();
Notice(Loop);
@@ -551,7 +597,8 @@ void Relooper::Calculate(Block *Entry) {
// For each entry, find the independent group reachable by it. The independent group is
// the entry itself, plus all the blocks it can reach that cannot be directly reached by another entry. Note that we
// ignore directly reaching the entry itself by another entry.
- void FindIndependentGroups(BlockSet &Blocks, BlockSet &Entries, BlockBlockSetMap& IndependentGroups) {
+ // @param Ignore - previous blocks that are irrelevant
+ void FindIndependentGroups(BlockSet &Entries, BlockBlockSetMap& IndependentGroups, BlockSet *Ignore=NULL) {
typedef std::map<Block*, Block*> BlockBlockMap;
struct HelperClass {
@@ -639,6 +686,7 @@ void Relooper::Calculate(Block *Entry) {
Block *Child = *iter;
for (BlockSet::iterator iter = Child->BranchesIn.begin(); iter != Child->BranchesIn.end(); iter++) {
Block *Parent = *iter;
+ if (Ignore && Ignore->find(Parent) != Ignore->end()) continue;
if (Helper.Ownership[Parent] != Helper.Ownership[Child]) {
ToInvalidate.push_back(Child);
}
@@ -756,7 +804,7 @@ void Relooper::Calculate(Block *Entry) {
// independent blocks from an entry/ies. It is important to remove through
// multiples as opposed to looping since the former is more performant.
BlockBlockSetMap IndependentGroups;
- FindIndependentGroups(Blocks, *Entries, IndependentGroups);
+ FindIndependentGroups(*Entries, IndependentGroups);
PrintDebug("Independent groups: %d\n", IndependentGroups.size());
@@ -903,10 +951,28 @@ void Relooper::Calculate(Block *Entry) {
});
}
+ void FindNaturals(Shape *Root, Shape *Otherwise=NULL) {
+ if (Root->Next) {
+ Root->Natural = Root->Next;
+ FindNaturals(Root->Next, Otherwise);
+ } else {
+ Root->Natural = Otherwise;
+ }
+
+ SHAPE_SWITCH(Root, {
+ }, {
+ for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
+ FindNaturals(iter->second, Root->Natural);
+ }
+ }, {
+ FindNaturals(Loop->Inner, Loop->Inner);
+ });
+ }
+
// Remove unneeded breaks and continues.
// A flow operation is trivially unneeded if the shape we naturally get to by normal code
// execution is the same as the flow forces us to.
- void RemoveUnneededFlows(Shape *Root, Shape *Natural=NULL) {
+ void RemoveUnneededFlows(Shape *Root, Shape *Natural=NULL, LoopShape *LastLoop=NULL) {
BlockSet NaturalBlocks;
FollowNaturalFlow(Natural, NaturalBlocks);
Shape *Next = Root;
@@ -928,16 +994,22 @@ void Relooper::Calculate(Block *Entry) {
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;
});
}
@@ -968,7 +1040,7 @@ void Relooper::Calculate(Block *Entry) {
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;
@@ -1006,6 +1078,7 @@ void Relooper::Calculate(Block *Entry) {
}
void Process(Shape *Root) {
+ FindNaturals(Root);
RemoveUnneededFlows(Root);
FindLabeledLoops(Root);
}
@@ -1053,6 +1126,10 @@ void Debugging::Dump(BlockSet &Blocks, const char *prefix) {
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 34b6db08..fe56a133 100644
--- a/src/relooper/Relooper.h
+++ b/src/relooper/Relooper.h
@@ -101,6 +101,7 @@ 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
+ 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 7da990b5..b2d500d7 100644
--- a/src/relooper/test.cpp
+++ b/src/relooper/test.cpp
@@ -231,5 +231,32 @@ int main() {
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 d657c6af..b3535592 100644
--- a/src/relooper/test.txt
+++ b/src/relooper/test.txt
@@ -136,3 +136,20 @@ while(1) {
// 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 696542ef..6049ee48 100644
--- a/src/relooper/test3.txt
+++ b/src/relooper/test3.txt
@@ -9,7 +9,7 @@ do {
}
} while(0);
LBB3
-L5: do {
+do {
if (LBB3 -> LBB4) {
LBB4
if (!(LBB4 -> LBB5)) {
@@ -18,7 +18,7 @@ L5: do {
while(1) {
LBB5
if (LBB5 -> LBB6) {
- break L5;
+ break;
}
}
}
diff --git a/src/relooper/test_inf.txt b/src/relooper/test_inf.txt
index 379d2083..1dff59bb 100644
--- a/src/relooper/test_inf.txt
+++ b/src/relooper/test_inf.txt
@@ -5,35 +5,33 @@ if (uint(i4) >= uint(i5)) {
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 @@ if (uint(i4) >= uint(i5)) {
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 @@ if (uint(i4) >= uint(i5)) {
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
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-08-05 07:00:16 +0000