Improve SSA topological sort (#15200)
authormikedn <onemihaid@hotmail.com>
Thu, 24 May 2018 19:01:41 +0000 (22:01 +0300)
committerSergey Andreenko <seandree@microsoft.com>
Thu, 24 May 2018 19:01:41 +0000 (12:01 -0700)
commitc0150d4d0131ab16a50378711d8adb19c5c868ab
treec9348a45267422da9e9256515e6a5504d3dbb3d6
parent78e7dbf21fe0b5fbe72332b7d8d1dcbd44d3186c
Improve SSA topological sort (#15200)

* Simplify block successor iterators

Construction of an end AllSuccessorIter requires the number of block successors. This can be avoided by keeping track of the number of remaining successors so that the end iterator is simply "0 remaining successors".

Remove StartAllSuccs & co. These functions don't do anything useful.

Since AllSuccessorIter and EHSuccessorIter now have similar constructors the "collection" classes AllSuccs and EHSuccs can be replaced by a single template class.

* Split out block successor iterator logic

The AllSuccessorIterator iterator is pretty large - 64 bytes on 64 bit hosts. When used as local variables that's not much of a problem but if they end up stored in containers then a lot of space is wasted.

AllSuccessorIter contains a pointer to the compiler object and a pointer to the block whose successors it iterates over. And then it also contains an EHSuccessorIter that contains the same 2 pointers.

In scenarios such as the one in SsaBuilder::TopologicalSort the compiler pointer need not be stored and the block needs to be stored only once and be made accessible so a separate block stack isn't needed.

This change splits out the successor iterating logic into separate "position" classes that receieve the compiler and block via function parameters.

* Improve TopologicalSort memory usage
src/jit/arraystack.h
src/jit/block.cpp
src/jit/block.h
src/jit/ssabuilder.cpp