[Dominators] Avoid potentially quadratic std::is_permutation
[Dominators] Avoid potentially quadratic std::is_permutation

Summary:
If the two sequences are not equal, std::is_permutation may be O(N^2)
and indeed the case in libstdc++ and libc++. Use SmallPtrSet to prevent
pessimizing cases. On my machine, SmallPtrSet starts to outperform
std::is_permutation when there are 16 elements.

Reviewers: kuhar

Reviewed By: kuhar

Subscribers: kristina, jdoerfert, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D58373

git-svn-id: 0ff597fd157e6f4fc38580e8d64ab130330d2411@355070 91177308-0d34-0410-b5e6-96231b3b80d8

apple/swift-llvm,GPUOpen-Drivers/llvm,apple/swift-llvm,llvm-mirror/llvm,GPUOpen-Drivers/llvm,llvm-mirror/llvm,llvm-mirror/llvm,llvm-mirror/llvm,apple/swift-llvm,llvm-mirror/llvm,apple/swift-llvm,GPUOpen-Drivers/llvm,GPUOpen-Drivers/llvm,llvm-mirror/llvm,llvm-mirror/llvm,apple/swift-llvm,apple/swift-llvm,GPUOpen-Drivers/llvm,GPUOpen-Drivers/llvm,GPUOpen-Drivers/llvm,apple/swift-llvm,llvm-mirror/llvm,llvm-mirror/llvm,GPUOpen-Drivers/llvm,apple/swift-llvm