If a threading path has cycles within it then the transformation is not
correct. This patch fixes a couple of cases that create such cycles.

Fixes https://github.com/llvm/llvm-project/issues/166868

The edge `StartBlock -> EndBlock` already exists before unfolding.

The instructions for `applyUpdates()` say that you are supposed not
to insert an existing edge.

Fixes issues reported by @mikaelholmen in
https://github.com/llvm/llvm-project/pull/162802

Note that the test coverage misses the dominator tree verification. This
patch controls verification by option, instead of using the
EXPENSIVE_CHECKS macro.

Issue #147390

Fixes #160250
We previously assumed the select to unfold is defined in the incoming
block of phi user, as `isValidSelectInst` filters other cases at the
initial stage. However, the selects not defined in the incoming block
may occur after unfolding the arms of the unfolded select.
This patch sinks the select into the incoming block of the phi user and
unfolds it at the incoming block.

…ect successor

Previously the code assumed that the select instruction is defined in a
block that is a direct predecessor of the block where the PHINode uses
it. So, we were hitting an assertion when we tried to access the def
block as an incoming block for the user phi node.

This patch handles that case by using the correct end block and creating
a new phi node that aggregates both the values of the select in that end
block, and then using that new unfolded phi to overwrite the original
user phi node.

Fixes #106083

Change-Id: Ie471994cca232318f74a6e6438efa21e561c2dc0

I tried to add a limit to number of blocks visited in the paths()
function but even with a very high limit the transformation coverage was
being reduced.

After looking at the code it seemed that the function was trying to
create paths of the form
`SwitchBB...DeterminatorBB...SwitchPredecessor`. This is inefficient
because a lot of nodes in those paths (nodes before DeterminatorBB)
would be irrelevant to the optimization. We only care about paths of the
form `DeterminatorBB_Pred DeterminatorBB...SwitchBB`. This weeds out a
lot of visited nodes.

In this patch I have added a hard limit to the number of nodes visited
and changed the algorithm for path calculation. Primarily I am
traversing the use-def chain for the PHI nodes that define the state. If
we have a hole in the use-def chain (no immediate predecessors) then I
call the paths() function.

I also had to the change the select instruction unfolding code to insert
redundant one input PHIs to allow the use of the use-def chain in
calculating the paths.

The test suite coverage with this patch (including a limit on nodes
visited) is as follows:

    Geomean diff:
      dfa-jump-threading.NumTransforms: +13.4%
      dfa-jump-threading.NumCloned: +34.1%
      dfa-jump-threading.NumPaths: -80.7%

Compile time effect vs baseline (pass enabled by default) is mostly
positive:
https://llvm-compile-time-tracker.com/compare.php?from=ad8705fda25f64dcfeb6264ac4d6bac36bee91ab&to=5a3af6ce7e852f0736f706b4a8663efad5bce6ea&stat=instructions:u

Change-Id: I0fba9e0f8aa079706f633089a8ccd4ecf57547ed

Fixes the buildbot failure in
https://github.com/llvm/llvm-project/pull/78134#issuecomment-1892195197
When we meet the path with single `determinator`, the determinator
actually takes itself as a predecessor. Thus, we need to let `Prev` be
the determinator when `PathBBs` has only one element.

Fixes #78059