StructurizeCFG: Use a reverse post-order traversal
authorTom Stellard <thomas.stellard@amd.com>
Wed, 4 Feb 2015 20:49:44 +0000 (20:49 +0000)
committerTom Stellard <thomas.stellard@amd.com>
Wed, 4 Feb 2015 20:49:44 +0000 (20:49 +0000)
commit7c038bc15f25f8505f0fa436044a59604b081883
tree525e3b171bb0a0142ac88a97fc9fad4deb2378c3
parent1d75b286e63156b8533dc09c895c6364b388491a
StructurizeCFG: Use a reverse post-order traversal

We were previously doing a post-order traversal and operating on the
list in reverse, however this would occasionaly cause backedges for
loops to be visited before some of the other blocks in the loop.

We know use a reverse post-order traversal, which avoids this issue.

The reverse post-order traversal is not completely ideal, so we need
to manually fixup the list to ensure that inner loop backedges are
visited before outer loop backedges.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@228186 91177308-0d34-0410-b5e6-96231b3b80d8
lib/Transforms/Scalar/StructurizeCFG.cpp
test/Transforms/StructurizeCFG/nested-loop-order.ll [new file with mode: 0644]
test/Transforms/StructurizeCFG/one-loop-multiple-backedges.ll
test/Transforms/StructurizeCFG/post-order-traversal-bug.ll [new file with mode: 0644]