Improve SSA dominator computation memory usage (#14965)
authormikedn <onemihaid@hotmail.com>
Wed, 15 Nov 2017 23:14:22 +0000 (01:14 +0200)
committerBruce Forstall <brucefo@microsoft.com>
Wed, 15 Nov 2017 23:14:22 +0000 (15:14 -0800)
commita7cf54f885f112eb76376eb32b5466f83dc2a3df
treef52002e87a19f2c0079a13f835b89ffc20363e30
parent6b4b00f0c4e654d6fb5cd52c16bf4cc7d1ab8263
Improve SSA dominator computation memory usage (#14965)

* Improve SSA DF computation memory usage

DF(b) can be stored in a vector instead of a hashtable (set). Nothing needs a O(1) membership test, the duplicates that may be generated during DF construction can be easily avoided by observing that:
* each block in the graph is processed exactly once
* during processing the block is added to the relevant DF vectors, at the end of each vector. If the same DF vector is encountered multiple times then checking if the block is already a member is trivial.

* Use the same block BitVec for topo sort and IDom

* Add BitVecOps::TryAddElemD

Makes the code more readable and avoids the duplicated IsShort test that a separate IsMember/AddElemD may generate.

* Improve SSA IDF computation memory usage

Like DF(b), IDF(b) can be stored in a vector if duplicates are avoided. This can be done by using a BitVector like TopologicalSort and ComputeImmediateDom already do. It's cheaper than using a hashtable (even though it requires a "clear" for every block that has a frontier).

Also, storing IDF(b) into a vector makes it easier to track newly added blocks - they're at the end of the vector. Using a separate "delta" set is no longer needed.
src/jit/bitsetasshortlong.h
src/jit/block.h
src/jit/compiler.h
src/jit/gentree.h
src/jit/jithashtable.h
src/jit/ssabuilder.cpp
src/jit/ssabuilder.h