tree b76ac79e88b593547d9ab85dccf3eda207d85125
parent 523f1d04204c15279935e534751860c85eb0686f
author Yunxing Dai <yunxing@google.com> 1584479460 -0700
committer TensorFlower Gardener <gardener@tensorflow.org> 1584479662 -0700

[XLA] Create explicit phi graph optimization during dataflow analysis.

Previously hlo dataflow analysis tries to create phi and remove phi at
the same time during propagation, which leads to several cases of
deadlocks, some are hard to fix. This cl changes this process to two phases:

1. During value propagation, Dataflow analysis always create phi
values once it see multiple inputs merging at the same point. It then
records those phi values as well as their inputs in a phi graph.

2. Post value propagation, Dataflow analysis can then do certain
optimization on the phi graph to prune uncessary phi nodes.

Both of the functions are guaranteed to exit thus we can avoid
deadlocks.

PiperOrigin-RevId: 301449515
Change-Id: I85f545ed9935ad5aee85b3f5bc05c2ba19da074a