[LLVMbugs] Smarter bugpoint reduction heuristic

[Domagoj Babic]

Modifications:

1) random_shuffle of TheList - decreases the probability of having
two bug causing functions at the opposite ends of a large list, speeds
up the convergence.

2) backtrack with 10% probability from the trimming loop
to the binary search loop - once it finds the problematic
cluster, the remaining functions are eliminated one by one,
which is painfully slow. This probabalistic backtracking enables
the bugpoint to leave the particularly hard search subspace
and attempt more agressive pruning again.

A bug that the previous heuristic couldn't reduce in a week
(after a week it was left with cca 6500 functions, reducing them
one by one...), the new one reduces in 1.5 hours to 4 functions,
and then takes another 2 hours for basic blocks and instructions.

This patch reduces the probability of heavy tails of the distribution,
speeding up the convergence.

Domagoj Babic
-------------- next part --------------
A non-text attachment was scrubbed...
Name: ListReducerPatch.bz2
Type: application/x-bzip2
Size: 1881 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20061010/a063f3df/attachment.bin>