aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lib/Target/JSBackend/Relooper.cpp114
-rw-r--r--lib/Target/JSBackend/Relooper.h14
2 files changed, 80 insertions, 48 deletions
diff --git a/lib/Target/JSBackend/Relooper.cpp b/lib/Target/JSBackend/Relooper.cpp
index 780a6d5930..ce9232d994 100644
--- a/lib/Target/JSBackend/Relooper.cpp
+++ b/lib/Target/JSBackend/Relooper.cpp
@@ -243,7 +243,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 +286,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 +312,28 @@ 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) {
+ if (UseSwitch) {
+ PrintIndented("L%d: ", Id);
+ } else {
+ 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 +342,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 +566,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 +872,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 +886,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 +1045,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 +1066,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 +1085,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);
}
}, {
@@ -1111,7 +1135,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);
@@ -1130,20 +1154,20 @@ 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);
}
Next = Multiple->Next;
}, {
@@ -1169,13 +1193,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 +1218,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 +1233,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 +1320,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");
diff --git a/lib/Target/JSBackend/Relooper.h b/lib/Target/JSBackend/Relooper.h
index 152bae0e6e..c86e63ac1f 100644
--- a/lib/Target/JSBackend/Relooper.h
+++ b/lib/Target/JSBackend/Relooper.h
@@ -132,8 +132,6 @@ struct SimpleShape : public Shape {
}
};
-typedef std::map<Block*, Shape*> BlockShapeMap;
-
// A shape that may be implemented with a labeled loop.
struct LabeledShape : public Shape {
bool Labeled; // If we have a loop, whether it needs to be labeled
@@ -141,12 +139,16 @@ struct LabeledShape : public Shape {
LabeledShape(ShapeType TypeInit) : Shape(TypeInit), Labeled(false) {}
};
+// Blocks with the same id were split and are identical, so we just care about ids in Multiple entries
+typedef std::map<int, Shape*> IdShapeMap;
+
struct MultipleShape : public LabeledShape {
- BlockShapeMap InnerMap; // entry block -> shape
- int NeedLoop; // If we have branches, we need a loop. This is a counter of loop requirements,
- // if we optimize it to 0, the loop is unneeded
+ IdShapeMap InnerMap; // entry block ID -> shape
+ int Breaks; // If we have branches on us, we need a loop (or a switch). This is a counter of requirements,
+ // if we optimize it to 0, the loop is unneeded
+ bool UseSwitch; // Whether to switch on label as opposed to an if-else chain
- MultipleShape() : LabeledShape(Multiple), NeedLoop(0) {}
+ MultipleShape() : LabeledShape(Multiple), Breaks(0), UseSwitch(false) {}
void RenderLoopPrefix();
void RenderLoopPostfix();
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-21 14:18:46 +0000