summaryrefslogtreecommitdiff
path: root/src/relooper/Relooper.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/relooper/Relooper.cpp')
-rw-r--r--src/relooper/Relooper.cpp122
1 files changed, 77 insertions, 45 deletions
diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp
index 780a6d59..9e469ec4 100644
--- a/src/relooper/Relooper.cpp
+++ b/src/relooper/Relooper.cpp
@@ -17,6 +17,10 @@
typedef std::string ministring;
#endif
+// uncomment these out to get LLVM errs() debugging support
+//#include <llvm/Support/raw_ostream.h>
+//using namespace llvm;
+
template <class T, class U> static bool contains(const T& container, const U& contained) {
return container.count(contained);
}
@@ -202,6 +206,7 @@ void Block::Render(bool InLoop) {
if (Fused) {
PrintDebug("Fusing Multiple to Simple\n");
Parent->Next = Parent->Next->Next;
+ Fused->UseSwitch = false; // TODO: emit switches here
Fused->RenderLoopPrefix();
// When the Multiple has the same number of groups as we have branches,
@@ -243,7 +248,7 @@ void Block::Render(bool InLoop) {
Details = ProcessedBranchesOut[DefaultTarget];
}
bool SetCurrLabel = (SetLabel && Target->IsCheckedMultipleEntry) || ForceSetLabel;
- bool HasFusedContent = Fused && contains(Fused->InnerMap, Target);
+ bool HasFusedContent = Fused && contains(Fused->InnerMap, Target->Id);
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
@@ -286,7 +291,7 @@ void Block::Render(bool InLoop) {
if (!First) Indenter::Indent();
Details->Render(Target, SetCurrLabel);
if (HasFusedContent) {
- Fused->InnerMap.find(Target)->second->Render(InLoop);
+ Fused->InnerMap.find(Target->Id)->second->Render(InLoop);
} else if (Details->Type == Branch::Nested) {
// Nest the parent content here, and remove it from showing up afterwards as Next
assert(Parent->Next);
@@ -312,18 +317,24 @@ void Block::Render(bool InLoop) {
// MultipleShape
void MultipleShape::RenderLoopPrefix() {
- if (NeedLoop) {
- if (Labeled) {
- PrintIndented("L%d: do {\n", Id);
+ if (Breaks) {
+ if (UseSwitch) {
+ if (Labeled) {
+ PrintIndented("L%d: ", Id);
+ }
} else {
- PrintIndented("do {\n");
+ if (Labeled) {
+ PrintIndented("L%d: do {\n", Id);
+ } else {
+ PrintIndented("do {\n");
+ }
+ Indenter::Indent();
}
- Indenter::Indent();
}
}
void MultipleShape::RenderLoopPostfix() {
- if (NeedLoop) {
+ if (Breaks && !UseSwitch) {
Indenter::Unindent();
PrintIndented("} while(0);\n");
}
@@ -332,32 +343,41 @@ void MultipleShape::RenderLoopPostfix() {
void MultipleShape::Render(bool InLoop) {
RenderLoopPrefix();
- // We know that blocks with the same Id were split from the same source, so their contents are identical and they are logically the same, so re-merge them here
- typedef std::map<int, Shape*> IdShapeMap;
- IdShapeMap IdMap;
- for (BlockShapeMap::iterator iter = InnerMap.begin(); iter != InnerMap.end(); iter++) {
- int Id = iter->first->Id;
- IdShapeMap::iterator Test = IdMap.find(Id);
- if (Test != IdMap.end()) {
- assert(Shape::IsSimple(iter->second) && Shape::IsSimple(Test->second)); // we can only merge simple blocks, something horrible has gone wrong if we see anything else
- continue;
+ if (!UseSwitch) {
+ // emit an if-else chain
+ bool First = true;
+ for (IdShapeMap::iterator iter = InnerMap.begin(); iter != InnerMap.end(); iter++) {
+ if (AsmJS) {
+ PrintIndented("%sif ((label|0) == %d) {\n", First ? "" : "else ", iter->first);
+ } else {
+ PrintIndented("%sif (label == %d) {\n", First ? "" : "else ", iter->first);
+ }
+ First = false;
+ Indenter::Indent();
+ iter->second->Render(InLoop);
+ Indenter::Unindent();
+ PrintIndented("}\n");
}
- IdMap[iter->first->Id] = iter->second;
- }
-
- bool First = true;
- for (IdShapeMap::iterator iter = IdMap.begin(); iter != IdMap.end(); iter++) {
+ } else {
+ // emit a switch
if (AsmJS) {
- PrintIndented("%sif ((label|0) == %d) {\n", First ? "" : "else ", iter->first);
+ PrintIndented("switch (label|0) {\n");
} else {
- PrintIndented("%sif (label == %d) {\n", First ? "" : "else ", iter->first);
+ PrintIndented("switch (label) {\n");
}
- First = false;
Indenter::Indent();
- iter->second->Render(InLoop);
+ for (IdShapeMap::iterator iter = InnerMap.begin(); iter != InnerMap.end(); iter++) {
+ PrintIndented("case %d: {\n", iter->first);
+ Indenter::Indent();
+ iter->second->Render(InLoop);
+ PrintIndented("break;\n");
+ Indenter::Unindent();
+ PrintIndented("}\n");
+ }
Indenter::Unindent();
PrintIndented("}\n");
}
+
RenderLoopPostfix();
if (Next) Next->Render(InLoop);
}
@@ -547,7 +567,7 @@ void Relooper::Calculate(Block *Entry) {
PriorOut->Ancestor = Ancestor;
PriorOut->Type = Type;
if (MultipleShape *Multiple = Shape::IsMultiple(Ancestor)) {
- Multiple->NeedLoop++; // We are breaking out of this Multiple, so need a loop
+ Multiple->Breaks++; // We are breaking out of this Multiple, so need a loop
}
iter++; // carefully increment iter before erasing
Target->BranchesIn.erase(Prior);
@@ -853,7 +873,7 @@ void Relooper::Calculate(Block *Entry) {
iter = Next; // increment carefully because Solipsize can remove us
}
}
- Multiple->InnerMap[CurrEntry] = Process(CurrBlocks, CurrEntries, NULL);
+ Multiple->InnerMap[CurrEntry->Id] = Process(CurrBlocks, CurrEntries, NULL);
// If we are not fused, then our entries will actually be checked
if (!Fused) {
CurrEntry->IsCheckedMultipleEntry = true;
@@ -867,6 +887,11 @@ void Relooper::Calculate(Block *Entry) {
NextEntries.insert(Entry);
}
}
+ // The multiple has been created, we can decide how to implement it
+ if (Multiple->InnerMap.size() >= 10) {
+ Multiple->UseSwitch = true;
+ Multiple->Breaks++; // switch captures breaks
+ }
return Multiple;
}
@@ -1021,7 +1046,7 @@ void Relooper::Calculate(Block *Entry) {
PostOptimizer(Relooper *ParentInit) : Parent(ParentInit), Closure(NULL) {}
#define RECURSE_Multiple(shape, func) \
- for (BlockShapeMap::iterator iter = shape->InnerMap.begin(); iter != shape->InnerMap.end(); iter++) { \
+ for (IdShapeMap::iterator iter = shape->InnerMap.begin(); iter != shape->InnerMap.end(); iter++) { \
func(iter->second); \
}
#define RECURSE_Loop(shape, func) \
@@ -1042,7 +1067,7 @@ void Relooper::Calculate(Block *Entry) {
SHAPE_SWITCH(S, {
Out.insert(Simple->Inner);
}, {
- for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
+ for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
FollowNaturalFlow(iter->second, Out);
}
FollowNaturalFlow(Multiple->Next, Out);
@@ -1061,7 +1086,7 @@ void Relooper::Calculate(Block *Entry) {
SHAPE_SWITCH(Root, {
}, {
- for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
+ for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
FindNaturals(iter->second, Root->Natural);
}
}, {
@@ -1072,7 +1097,7 @@ void Relooper::Calculate(Block *Entry) {
// 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, LoopShape *LastLoop=NULL) {
+ void RemoveUnneededFlows(Shape *Root, Shape *Natural=NULL, LoopShape *LastLoop=NULL, unsigned Depth=0) {
BlockSet NaturalBlocks;
FollowNaturalFlow(Natural, NaturalBlocks);
Shape *Next = Root;
@@ -1083,7 +1108,7 @@ void Relooper::Calculate(Block *Entry) {
if (Simple->Inner->BranchVar) LastLoop = NULL; // a switch clears out the loop (TODO: only for breaks, not continue)
if (Simple->Next) {
- if (!Simple->Inner->BranchVar && Simple->Inner->ProcessedBranchesOut.size() == 2) {
+ if (!Simple->Inner->BranchVar && Simple->Inner->ProcessedBranchesOut.size() == 2 && Depth < 20) {
// If there is a next block, we already know at Simple creation time to make direct branches,
// and we can do nothing more in general. But, we try to optimize the case of a break and
// a direct: This would normally be if (break?) { break; } .. but if we
@@ -1111,7 +1136,7 @@ void Relooper::Calculate(Block *Entry) {
if (Details->Type == Branch::Break) {
Details->Type = Branch::Direct;
if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) {
- Multiple->NeedLoop--;
+ Multiple->Breaks--;
}
} else {
assert(Details->Type == Branch::Direct);
@@ -1119,6 +1144,7 @@ void Relooper::Calculate(Block *Entry) {
}
}
}
+ Depth++; // this optimization increases depth, for us and all our next chain (i.e., until this call returns)
}
Next = Simple->Next;
} else {
@@ -1130,24 +1156,24 @@ void Relooper::Calculate(Block *Entry) {
if (Details->Type != Branch::Direct && contains(NaturalBlocks, Target)) { // note: cannot handle split blocks
Details->Type = Branch::Direct;
if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) {
- Multiple->NeedLoop--;
+ Multiple->Breaks--;
}
} 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--;
+ Multiple->Breaks--;
}
}
}
}
}, {
- for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
- RemoveUnneededFlows(iter->second, Multiple->Next, Multiple->NeedLoop ? NULL : LastLoop);
+ for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
+ RemoveUnneededFlows(iter->second, Multiple->Next, Multiple->Breaks ? NULL : LastLoop, Depth+1);
}
Next = Multiple->Next;
}, {
- RemoveUnneededFlows(Loop->Inner, Loop->Inner, Loop);
+ RemoveUnneededFlows(Loop->Inner, Loop->Inner, Loop, Depth+1);
Next = Loop->Next;
});
}
@@ -1169,13 +1195,16 @@ void Relooper::Calculate(Block *Entry) {
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) {
+ if (Fused && Fused->Breaks) {
LoopStack.push(Fused);
}
if (Simple->Inner->BranchVar) {
LoopStack.push(NULL); // a switch means breaks are now useless, push a dummy
}
if (Fused) {
+ if (Fused->UseSwitch) {
+ LoopStack.push(NULL); // a switch means breaks are now useless, push a dummy
+ }
RECURSE_Multiple(Fused, FindLabeledLoops);
}
for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {
@@ -1191,10 +1220,13 @@ void Relooper::Calculate(Block *Entry) {
}
}
}
+ if (Fused && Fused->UseSwitch) {
+ LoopStack.pop();
+ }
if (Simple->Inner->BranchVar) {
LoopStack.pop();
}
- if (Fused && Fused->NeedLoop) {
+ if (Fused && Fused->Breaks) {
LoopStack.pop();
}
if (Fused) {
@@ -1203,11 +1235,11 @@ void Relooper::Calculate(Block *Entry) {
Next = Root->Next;
}
}, {
- if (Multiple->NeedLoop) {
+ if (Multiple->Breaks) {
LoopStack.push(Multiple);
}
RECURSE(Multiple, FindLabeledLoops);
- if (Multiple->NeedLoop) {
+ if (Multiple->Breaks) {
LoopStack.pop();
}
Next = Root->Next;
@@ -1290,8 +1322,8 @@ void Debugging::Dump(Shape *S, const char *prefix) {
printf("<< Simple with block %d\n", Simple->Inner->Id);
}, {
printf("<< Multiple\n");
- for (BlockShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
- printf(" with entry %d\n", iter->first->Id);
+ for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) {
+ printf(" with entry %d\n", iter->first);
}
}, {
printf("<< Loop\n");
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-09-05 01:36:46 +0000