Fix infinite simulation cycles in SSA propagator.
authorDiego Novillo <dnovillo@google.com>
Fri, 5 Jan 2018 14:34:18 +0000 (09:34 -0500)
committerDiego Novillo <dnovillo@google.com>
Fri, 5 Jan 2018 15:29:39 +0000 (10:29 -0500)
commit716718a5e969f6b4e73cbc864db59a754a83aab3
treede2436deb14c08ad63cd5e4b498db00cd44cfe16
parent120ddffb41ef546aeaae7fbb7e50714f64553377
Fix infinite simulation cycles in SSA propagator.

This fixes https://github.com/KhronosGroup/SPIRV-Tools/issues/1159.  I
had missed a nuance in the original algorithm.  When simulating Phi
instructions, the SSA edges out of a Phi instruction should never be
added to the list of edges to simulate.

Phi instructions can be in SSA def-use cycles with other Phi
instructions.  This was causing the propagator to fall into an infinite
loop when the same def-use edge kept being added to the queue.

The original algorithm in the paper specifically separates the visit of
a Phi instruction vs the visit of a regular instruction.  This fix makes
the implementation match the original algorithm.
source/opt/propagator.cpp
source/opt/propagator.h
test/opt/ccp_test.cpp