The performance results of that paper are dubious. There is a followup paper by Georgiadis, Tarjan, and Werneck, entitled "Finding Dominators in Practice", which presents results to the contrary and quotes private communication from Cooper saying that he retested with a more careful implementation of Lengauer-Tarjan and found the same.
I went and found all of the tricks and optimizations I could find for LLVM's implementation of Lengauer-Tarjan. There are still some things that could probably be improved for a few percentage points of extra performance. Cameron On Oct 24, 2011, at 8:49 PM, Guoping Long wrote: > Thanks for pointing out this. I shall do the refactoring. > > Chris, why do you think this implementation is slower than the version in > llvm/Analysis (based on the classical Lengauer-Tarjan algorithm)? My patch > was based on this 2001 paper: K. D. Cooper "A Simple, Fast Dominance > Algorithm", which actually included an interesting analysis and comparison > with the classical Lengauer-Tarjan algorithm. I believe the implementation in > core LLVM shall be very stable and efficient. I am just interested in know > why choosing this. _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
