hasPredecessorHelper uses SmallPtrSet for the Visted data structure.
SmallPtrSet assumes it's size is less than 32 but can grow as large
as there is memory. When it does grow, the rehashing of it's large
table is very expensive.
By instrumenting hasPredecessorHelp and printing at the final Visited
size for a llvm+clang build, it was seen that nearly all of the
Visited's were less than 16.
In a 'small' 2000 line test case, when the Visited size was 1200,
the compile time 2 minutes. Now is down to 1 sec.
Only the function causing the problem was changed.
If anyone is interested in the instrumented data / histograms contact me offline.