diff options
author | Alon Zakai <alonzakai@gmail.com> | 2014-05-20 10:23:11 -0700 |
---|---|---|
committer | Alon Zakai <alonzakai@gmail.com> | 2014-05-20 10:23:11 -0700 |
commit | 881f94c087e4417c874dc136d01c31011c24684f (patch) | |
tree | a00fd8e78da47ea21fe289dbc294ca61e010cfb1 | |
parent | 1c8f88f0f870716be6ec0ce76770dc007621016f (diff) |
do not optimize out breaks if it causes excessive nesting
-rw-r--r-- | src/relooper/Relooper.cpp | 9 | ||||
-rw-r--r-- | src/relooper/test.cpp | 31 | ||||
-rw-r--r-- | src/relooper/test.txt | 153 |
3 files changed, 189 insertions, 4 deletions
diff --git a/src/relooper/Relooper.cpp b/src/relooper/Relooper.cpp index 568dd381..9e469ec4 100644 --- a/src/relooper/Relooper.cpp +++ b/src/relooper/Relooper.cpp @@ -1097,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; @@ -1108,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 @@ -1144,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 { @@ -1168,11 +1169,11 @@ void Relooper::Calculate(Block *Entry) { } }, { for (IdShapeMap::iterator iter = Multiple->InnerMap.begin(); iter != Multiple->InnerMap.end(); iter++) { - RemoveUnneededFlows(iter->second, Multiple->Next, Multiple->Breaks ? NULL : LastLoop); + 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; }); } diff --git a/src/relooper/test.cpp b/src/relooper/test.cpp index 9f3ddceb..f319757b 100644 --- a/src/relooper/test.cpp +++ b/src/relooper/test.cpp @@ -1,4 +1,6 @@ +#include <vector> + #include "Relooper.h" int main() { @@ -435,5 +437,34 @@ int main() { puts(r.GetOutputBuffer()); } + + if (1) { + Relooper::MakeOutputBuffer(10); + + printf("\n\n-- lots of exits to an unwind block, possible nesting --\n\n"); + + const int DEPTH = 40; + + std::vector<Block*> blocks; + for (int i = 0; i < DEPTH; i++) blocks.push_back(new Block("// block\n", NULL)); + Block *last = new Block("// last\nreturn;\n", NULL); + Block *UW = new Block("// UW\nresumeException();\n\n", NULL); + + for (int i = 0; i < DEPTH; i++) { + Block *b = blocks[i]; + b->AddBranchTo(i+1 < DEPTH ? blocks[i+1] : last, "check()", NULL); + b->AddBranchTo(UW, NULL, NULL); + } + + Relooper r; + for (int i = 0; i < DEPTH; i++) r.AddBlock(blocks[i]); + r.AddBlock(last); + r.AddBlock(UW); + + r.Calculate(blocks[0]); + r.Render(); + + puts(r.GetOutputBuffer()); + } } diff --git a/src/relooper/test.txt b/src/relooper/test.txt index d53aeeb1..2ae331c0 100644 --- a/src/relooper/test.txt +++ b/src/relooper/test.txt @@ -417,3 +417,156 @@ } // block D + + +-- lots of exits to an unwind block, possible nesting -- + + // block + do { + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (check()) { + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // block + if (!(check())) { + break; + } + // last + return; + } + } + } + } + } + } + } + } + } + } + } + } + } + } + } + } + } + } + } + } while(0); + // UW + resumeException(); + + |