David Callahan via llvm-dev
2016-Jun-30 15:31 UTC
[llvm-dev] New Aggressive Dead Code Elimination (updated)
I request additional review of diff: http://reviews.llvm.org/D18762 We noticed that a source of performance difference between llvm and gcc was in dead code elimination. This diff replaces ADCE with a new implementation which will remove control flow and, under option, also remove may-be-infinite loops which are dead. The patch current has "ADCE_new.h" and "ADCE_new.cpp" to clarify that this is essentially a full rewrite of the deleted "ADCE.h" and "ADCE.cpp", When ready to land, I plan to change these names back to the originals. The new algorithm uses the iterated dominance frontier to incrementally identify control dependence sources for live operations to determine when branch operations are live. It adds a new fix-up phase to correct update phi-nodeswhen control flow changes. Below are compile time and performance impacts based on Facebook internal code sets. Baseline ADCE compared to new ADCE compile time, -O3 removing loops Comparing compile times for ~400 source files from folly code base "baseline" is total time in seconds for all files "net_difference" is increase due to changes "percent" is increase expressed aa persent of baseline "samples" is number of distinct tests, these vary in some cases as runs with high variance in timing are excluded from summary baseline net_difference percent samples . 28,591.41 165.91 0.58 413 . Baseline ADCE compared with new ADCE, also removing loops baseline net_difference percent samples . 28,591.02 215.35 0.75 411 . Here are the impacts on runtimes for three different internal sets of benchmarks, again compiled -O3 baseline, percent, samples as above Without removing loops: baseline total samples . 105,846,951,721,178.10 1.000 85 . 28,317,122,801,690.20 0.998 288 . 364,771,688,928.16 0.997 64 . With removing loops: (adding -mllvm -adce-remove-loops) baseline total samples . 105,845,678,704,074.98 1.000 78 . 29,901,291,181,631.10 0.988 280 . 332,140,718,056.76 0.982 61 .