Page MenuHomePhabricator

[SCCP] Keep track of functions that might contain undef values.
Needs ReviewPublic

Authored by fhahn on Feb 13 2020, 2:02 AM.

Details

Summary

This patch adds coarse grain tracking of functions which may contain
undefined values. It does so be keeping a SetVector of functions that
may containe undefined values. Whenever a new block is marked as
executable, the function is marked as containing possibly undefined
values.

To resolve undefined values, we just look at the last function in
PossiblyUndefinedFns and call ResolvedUndefsIn. If it returns false,
that means the function does not contain undefined values and we can
remote it from the set.

We use the fact that once we know the executable blocks of a function do
not contain undefined values, the only way the function can contain
undefined values is when a new block gets marked as executable.

The book-keeping overhead should be very small (we access
PossiblyUndefinedFns once per basic block in the module) and the gains
in terms of avoided ResolvedUndefsIn calls seem quite promising:

For -O3 build of SPEC2006,SPEC2000,MultiSource, we get the following
improvements for the number of times ResolvedUndefsIn is called. Below
the top15 improvements:

base    patch

test-suite...arks/BitBench/drop3/drop3.test 23.00 6.00 -73.9%
test-suite...arks/VersaBench/dbms/dbms.test 393.00 103.00 -73.8%
test-suite...patricia/network-patricia.test 42.00 12.00 -71.4%
test-suite...math/automotive-basicmath.test 34.00 10.00 -70.6%
test-suite...000/186.crafty/186.crafty.test 746.00 224.00 -70.0%
test-suite...rks/FreeBench/mason/mason.test 69.00 21.00 -69.6%
test-suite...lications/sqlite3/sqlite3.test 7253.00 2221.00 -69.4%
test-suite...ks/Prolangs-C/gnugo/gnugo.test 176.00 54.00 -69.3%
test-suite...TimberWolfMC/timberwolfmc.test 1472.00 452.00 -69.3%
test-suite...quoia/CrystalMk/CrystalMk.test 39.00 12.00 -69.2%
test-suite...s/ASC_Sequoia/IRSmk/IRSmk.test 32.00 10.00 -68.8%
test-suite...eeBench/analyzer/analyzer.test 98.00 32.00 -67.3%
test-suite...s/MallocBench/cfrac/cfrac.test 421.00 140.00 -66.7%
test-suite...lowfish/security-blowfish.test 58.00 20.00 -65.5%
test-suite...T2000/300.twolf/300.twolf.test 1102.00 382.00 -65.3%

For -O3 with LTO:

base    patch

test-suite...-typeset/consumer-typeset.test 14327.00 1541.00 -89.2%
test-suite...arks/BitBench/drop3/drop3.test 43.00 10.00 -76.7%
test-suite...CFP2000/177.mesa/177.mesa.test 13321.00 3465.00 -74.0%
test-suite...patricia/network-patricia.test 68.00 18.00 -73.5%
test-suite...TimberWolfMC/timberwolfmc.test 2386.00 673.00 -71.8%
test-suite...5/124.m88ksim/124.m88ksim.test 3023.00 861.00 -71.5%
test-suite...arks/VersaBench/dbms/dbms.test 576.00 165.00 -71.4%
test-suite...lications/sqlite3/sqlite3.test 10248.00 2968.00 -71.0%
test-suite...math/automotive-basicmath.test 51.00 15.00 -70.6%
test-suite...000/186.crafty/186.crafty.test 1277.00 382.00 -70.1%
test-suite.../Benchmarks/Ptrdist/ks/ks.test 123.00 37.00 -69.9%
test-suite...ks/McCat/04-bisect/bisect.test 63.00 20.00 -68.3%
test-suite...rks/FreeBench/mason/mason.test 85.00 27.00 -68.2%
test-suite...ks/Prolangs-C/gnugo/gnugo.test 280.00 89.00 -68.2%
test-suite.../CINT2006/403.gcc/403.gcc.test 54981.00 17523.00 -68.1%

Diff Detail

Unit TestsFailed

TimeTest
20 msLLVM.Bindings/Go::Unknown Unit Message ("")
Script: -- : 'RUN: at line 1'; llvm-go test llvm.org/llvm/bindings/go/llvm