aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/relooper/Relooper.cpp51
-rw-r--r--src/relooper/Relooper.h8
-rw-r--r--src/relooper/test.cpp90
-rw-r--r--src/relooper/test.txt39
4 files changed, 180 insertions, 8 deletions
diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp
index c11de099..c6830158 100644
--- a/src/relooper/Relooper.cpp
+++ b/src/relooper/Relooper.cpp
@@ -122,7 +122,7 @@ void Branch::Render(Block *Target, bool SetLabel) {
if (Code) PrintIndented("%s\n", Code);
if (SetLabel) PrintIndented("label = %d;\n", Target->Id);
if (Ancestor) {
- if (Type != Direct) {
+ if (Type == Break || Type == Continue) {
if (Labeled) {
PrintIndented("%s L%d;\n", Type == Break ? "break" : "continue", Ancestor->Id);
} else {
@@ -287,6 +287,11 @@ void Block::Render(bool InLoop) {
Details->Render(Target, SetCurrLabel);
if (HasFusedContent) {
Fused->InnerMap.find(Target)->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);
+ Parent->Next->Render(InLoop);
+ Parent->Next = NULL;
}
if (useSwitch && iter != ProcessedBranchesOut.end()) {
PrintIndented("break;\n");
@@ -1077,12 +1082,48 @@ void Relooper::Calculate(Block *Entry) {
SHAPE_SWITCH(Root, {
if (Simple->Inner->BranchVar) LastLoop = NULL; // a switch clears out the loop (TODO: only for breaks, not continue)
- // If there is a next block, we already know at Simple creation time to make direct branches,
- // and we can do nothing more. If there is no next however, then Natural is where we will
- // go to by doing nothing, so we can potentially optimize some branches to direct.
if (Simple->Next) {
+ if (!Simple->Inner->BranchVar && Simple->Inner->ProcessedBranchesOut.size() == 2) {
+ // 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
+ // make sure to nest the else, we can save the break, if (!break?) { .. } . This is also
+ // better because the more canonical nested form is easier to further optimize later. The
+ // downside is more nesting, which adds to size in builds with whitespace.
+ // Note that we avoid switches, as it complicates control flow and is not relevant
+ // for the common case we optimize here.
+ bool Found = false;
+ bool Abort = false;
+ for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {
+ Block *Target = iter->first;
+ Branch *Details = iter->second;
+ if (Details->Type == Branch::Break) {
+ Found = true;
+ if (!contains(NaturalBlocks, Target)) Abort = true;
+ } else if (Details->Type != Branch::Direct) {
+ Abort = true;
+ }
+ }
+ if (Found && !Abort) {
+ for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {
+ Block *Target = iter->first;
+ Branch *Details = iter->second;
+ if (Details->Type == Branch::Break) {
+ Details->Type = Branch::Direct;
+ if (MultipleShape *Multiple = Shape::IsMultiple(Details->Ancestor)) {
+ Multiple->NeedLoop--;
+ }
+ } else {
+ assert(Details->Type == Branch::Direct);
+ Details->Type = Branch::Nested;
+ }
+ }
+ }
+ }
Next = Simple->Next;
} else {
+ // If there is no next then Natural is where we will
+ // go to by doing nothing, so we can potentially optimize some branches to direct.
for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {
Block *Target = iter->first;
Branch *Details = iter->second;
@@ -1140,7 +1181,7 @@ void Relooper::Calculate(Block *Entry) {
for (BlockBranchMap::iterator iter = Simple->Inner->ProcessedBranchesOut.begin(); iter != Simple->Inner->ProcessedBranchesOut.end(); iter++) {
Block *Target = iter->first;
Branch *Details = iter->second;
- if (Details->Type != Branch::Direct) {
+ if (Details->Type == Branch::Break || Details->Type == Branch::Continue) {
assert(LoopStack.size() > 0);
if (Details->Ancestor != LoopStack.top() && Details->Labeled) {
LabeledShape *Labeled = Shape::IsLabeled(Details->Ancestor);
diff --git a/src/relooper/Relooper.h b/src/relooper/Relooper.h
index 85adf359..152bae0e 100644
--- a/src/relooper/Relooper.h
+++ b/src/relooper/Relooper.h
@@ -24,9 +24,11 @@ struct Shape;
// Info about a branching from one block to another
struct Branch {
enum FlowType {
- Direct = 0, // We will directly reach the right location through other means, no need for continue or break
+ Direct = 0, // We will directly reach the right location through other means, no need for continue or break
Break = 1,
- Continue = 2
+ Continue = 2,
+ Nested = 3 // This code is directly reached, but we must be careful to ensure it is nested in an if - it is not reached
+ // unconditionally, other code paths exist alongside it that we need to make sure do not intertwine
};
Shape *Ancestor; // If not NULL, this shape is the relevant one for purposes of getting to the target block. We break or continue on it
Branch::FlowType Type; // If Ancestor is not NULL, this says whether to break or continue
@@ -59,7 +61,7 @@ struct Block {
Shape *Parent; // The shape we are directly inside
int Id; // A unique identifier, defined when added to relooper. Note that this uniquely identifies a *logical* block - if we split it, the two instances have the same content *and* the same Id
const char *Code; // The string representation of the code in this block. Owning pointer (we copy the input)
- const char *BranchVar; // If we have more than one branch out, the variable whose value determines where we go
+ const char *BranchVar; // A variable whose value determines where we go; if this is not NULL, emit a switch on that variable
bool IsCheckedMultipleEntry; // If true, we are a multiple entry, so reaching us requires setting the label variable
Block(const char *CodeInit, const char *BranchVarInit);
diff --git a/src/relooper/test.cpp b/src/relooper/test.cpp
index b4ce669c..2b25001b 100644
--- a/src/relooper/test.cpp
+++ b/src/relooper/test.cpp
@@ -314,5 +314,95 @@ int main() {
puts(buffer);
}
+
+ if (1) {
+ Relooper::MakeOutputBuffer(10);
+
+ printf("\n\n-- If chain (optimized) --\n\n");
+
+ Block *b_a = new Block("// block A\n", NULL);
+ Block *b_b = new Block("// block B\n", NULL);
+ Block *b_c = new Block("// block C\n", NULL);
+
+ b_a->AddBranchTo(b_b, "a == 10", NULL);
+ b_a->AddBranchTo(b_c, NULL, NULL);
+
+ b_b->AddBranchTo(b_c, NULL, NULL);
+
+ Relooper r;
+ r.AddBlock(b_a);
+ r.AddBlock(b_b);
+ r.AddBlock(b_c);
+
+ r.Calculate(b_a);
+ r.Render();
+
+ puts(r.GetOutputBuffer());
+ }
+
+ if (1) {
+ Relooper::MakeOutputBuffer(10);
+
+ printf("\n\n-- If chain (optimized) --\n\n");
+
+ Block *b_a = new Block("// block A\n", NULL);
+ Block *b_b = new Block("// block B\n", NULL);
+ Block *b_c = new Block("// block C\n", NULL);
+ Block *b_d = new Block("// block D\n", NULL);
+
+ b_a->AddBranchTo(b_b, "a == 10", NULL);
+ b_a->AddBranchTo(b_d, NULL, NULL);
+
+ b_b->AddBranchTo(b_c, "b == 10", NULL);
+ b_b->AddBranchTo(b_d, NULL, NULL);
+
+ b_c->AddBranchTo(b_d, NULL, NULL);
+
+ Relooper r;
+ r.AddBlock(b_a);
+ r.AddBlock(b_b);
+ r.AddBlock(b_c);
+ r.AddBlock(b_d);
+
+ r.Calculate(b_a);
+ r.Render();
+
+ puts(r.GetOutputBuffer());
+ }
+
+ if (1) {
+ Relooper::MakeOutputBuffer(10);
+
+ printf("\n\n-- If chain (optimized, long) --\n\n");
+
+ Block *b_a = new Block("// block A\n", NULL);
+ Block *b_b = new Block("// block B\n", NULL);
+ Block *b_c = new Block("// block C\n", NULL);
+ Block *b_d = new Block("// block D\n", NULL);
+ Block *b_e = new Block("// block E\n", NULL);
+
+ b_a->AddBranchTo(b_b, "a == 10", NULL);
+ b_a->AddBranchTo(b_e, NULL, NULL);
+
+ b_b->AddBranchTo(b_c, "b == 10", NULL);
+ b_b->AddBranchTo(b_e, NULL, NULL);
+
+ b_c->AddBranchTo(b_d, "c == 10", NULL);
+ b_c->AddBranchTo(b_e, NULL, NULL);
+
+ b_d->AddBranchTo(b_e, NULL, NULL);
+
+ Relooper r;
+ r.AddBlock(b_a);
+ r.AddBlock(b_b);
+ r.AddBlock(b_c);
+ r.AddBlock(b_d);
+ r.AddBlock(b_e);
+
+ r.Calculate(b_a);
+ r.Render();
+
+ puts(r.GetOutputBuffer());
+ }
}
diff --git a/src/relooper/test.txt b/src/relooper/test.txt
index 82b02ad7..1fa205ba 100644
--- a/src/relooper/test.txt
+++ b/src/relooper/test.txt
@@ -360,3 +360,42 @@
}
}
+
+
+-- If chain (optimized) --
+
+ // block A
+ if (a == 10) {
+ // block B
+ }
+ // block C
+
+
+
+-- If chain (optimized) --
+
+ // block A
+ if (a == 10) {
+ // block B
+ if (b == 10) {
+ // block C
+ }
+ }
+ // block D
+
+
+
+-- If chain (optimized, long) --
+
+ // block A
+ if (a == 10) {
+ // block B
+ if (b == 10) {
+ // block C
+ if (c == 10) {
+ // block D
+ }
+ }
+ }
+ // block E
+
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2024-11-22 07:21:57 +0000