PollyProf - The Potential of Polyhedral Optimization: An Empirical Study

Analysis Framework

The analysis framework we used is a Makefile based system that instruments projects provided in LLVM-IR and executes a defined set of test-cases for each testing class (Standard, Dynamic, Extended). You can get the source of the framework

• pprof - coverage analysis

The archive contains all programs tested with our empirical study, as well as Makefile scripts to execute benchmarks and arbitrary test inputs on these binaries.

Setup

The study can be configured via changes to Makefile.config. Imortant variables are:

• POLLY

  - Set this to the location of LLVMPolly.so.

• PAPI_FLAGS

  - Make sure -L points to papi's lib dir.

• PROFILING_FLAGS

  - Make sure -L points to polly's lib dir.

• PAPI_CALIBRATION

  - Enter the average time of a timing call, obtained by compiling stack.c in calibration mode (Documentation on how to do this follows)

• VERBOSE

  (recommended) Set this to 1, if you like to see verbose output.

Prepare the measurement

The user who runs our analysis framework needs permission to execute processes with the SCHED_FIFO priority queue (see /etc/security/limits.conf). If you don't want to execute within SCHED_FIFO (timings can be wrong/inconsistent) adapt the script test.sh in the top-level directory of the study. You need to change the following line:

exec /usr/bin/time -f "%U,%S,%e" -a -o ${TIME} taskset 0x00000001 chrt -f 20 ${REAL_PROG} $*

to this:

exec /usr/bin/time -f "%U,%S,%e" -a -o ${TIME} taskset 0x00000001 ${REAL_PROG} $*

The download above already contains this change, as usually a user is not allowed to execute in SCHED_FIFO.

Run the analysis

Makre sure the variables are set up properly

• LD_LIBRARY_PATH

  - You need to have everything to run Polly in this path (usually the required paths are: cloog's libdir, isl's libdir, polly's libdir.

• PATH

  - You need to be able to run LLVM's tools (opt, clang) and polly-prof. Usually this requires the bindir of your LLVM installation.

are set up to contain: Make sure polly-prof and our modified LLVM is available in your PATH and execute:

make report -i

Make sure it starts spending some time on the opt tool instead of throwing up on errors. With VERBOSE enabled you should see the following

mkdir -p std
clang -Xclang -load -Xclang ......

proceeding without errors. This can take a while (Expect at least 1 day). This builds the binaries for each testing class, executes the tests and generates the required report files. Ignoring the errors is necessary for now, as some tests may return error codes, which we do not ignore properly in our Makefiles yet. Afterwards you can generate the merged data set (as shown below) by executing:

make diagrams

Compiled results

The compressed results can be found in the following table:

Raw data

The table above was generated using the following raw data, generated with our empirical analysis framework.

Name	SthDyn	Tsth	JitDyn	Tjit	ExtDyn	Text	Traw	Domain	Tsth_papi	Tjit_papi	Text_papi	CallsSth	CallsJit	CallsExt
xlintstrfs	5.95973	2.76184	55.22496	14.827	55.23710	15.8773	2.54	Scientific	0.192564	9.25948	10.1506	637225	30641060	33589806
postgres	24.17302	269.436	26.14105	288.371	44.57173	415.866	0	Database	102.599	115.661	227.514	339515698	382739705	752878654
xlintstc	0	0	0	0	0	0	15.4	Scientific	0	0	0	0	0	0
xeigtstc	6.57484	16.0237	52.18159	54.0137	52.58918	65.1043	13.86	Scientific	1.49777	31.1426	40.3936	4956361	103055791	133668552
povray	15.43327	453.036	27.61837	631.992	90.47926	781.402	313.86	Multimedia	104.997	247.075	361.544	347450455	817609283	1196404573
hmac	5.64516	0.000248	11.00917	0.000109	11.88811	0.000143	0	Encryption	6.04384	6.04384	6.04384	20	20	20
linpack	5.80931	16.005	85.20705	16.8062	85.12940	16.6747	33.91	Scientific	0.717772	1.25665	1.266	2375220	4158441	4189389
gzip	2.57704	12.0738	3.76825	12.4336	36.45602	38.2774	12.58	Compression	0.0637495	0.30444	19.8129	210957	1007439	65563979
md5	1.32626	0.000377	5.67376	0.000141	4.22535	0.000142	0	Encryption	2.11534	2.11534	2.11534	7	7	7
python	0	0	0	0	0	0	0	Compilation	12.6024	0	0	41703325	0	0
xlintstd	0	0	0	0	0	0	8.51	Scientific	0	0	0	0	0	0
xlintstds	5.44038	2.31245	64.44604	9.33249	64.59700	9.7576	2.26	Scientific	0.0185676	4.97591	5.07073	61443	16466067	16779837
xeigtstd	9.59238	15.0119	50.40474	61.4302	50.74562	73.7825	12.43	Scientific	1.95311	37.7003	47.2897	6463129	124756077	156488853
ccrypt	0.33820	0.121526	13.73429	0.163241	45.33950	0.944073	0	Encryption	0.000279225	0.0331768	0.668482	924	109787	2212110
rc4	0.00000	6.4e-05	0.00000	6.6e-05	0.00000	6.4e-05	0	Encryption	0	0	0	0	0	0
xlintstz	0	0	0	0	0	0	16.74	Scientific	0	0	0	0	0	0
xeigtstz	4.83016	20.4258	50.74581	60.8055	51.30749	72.7804	17.97	Scientific	1.44406	32.6784	42.1661	4778634	108137757	139534156
crocopat	3.50389	226.871	5.21768	229.531	19.50857	343.771	149.53	Verification	11.7159	18.3776	99.0732	38769759	60814288	327848585
xlintstrfc	2.09424	6.72188	49.90069	19.1694	50.87336	20.8655	6	Scientific	0.191467	9.81101	10.996	633593	32466138	36387500
mcrypt-ciphers	11.50099	0.051726	12.90004	0.053589	37.90083	0.137807	0.02	Encryption	0.00941056	0.0108442	0.0770653	31141	35885	255021
sha512	71.21680	0.023003	88.18521	0.028422	87.79217	0.029563	0.01	Encryption	0.00472568	0.00892585	0.00892585	15638	29537	29537
leveldb	1.36778	0.057904	1.74968	0.0771	0	0.076118	58.83	Database	0.000612241	0.00110361	3.88717	2026	3652	12863243
blowfish	0.00000	0.003017	0.84884	0.003063	0.94248	0.003077	0	Encryption	0	1.90381	2.02469	0	63	67
minisat	6.58218	2655.72	6.57247	2668.53	9.97142	2893.98	2335.83	Verification	252.54	252.917	435.466	835695037	836940624	1441023730
sha1	0.06576	0.004562	89.31739	0.004849	88.34633	0.004874	0	Encryption	6.04384	0.000568423	0.000568423	2	1881	1881
des	1.07527	0.000372	1.12994	0.000354	36.01504	0.00133	0	Encryption	6.04384	1.20877	0.000761222	2	4	2519
lulesh-omp	44.00141	1281.38	46.65814	1660.75	48.11050	1905.93	280.31	Simulation	782.198	1111.54	1317.5	2588412803	3678269354	4359801901
js	0.31426	6.08196	21.21456	10.831	37.79989	25.7524	5.9	Compilation	0.0243537	3.47768	15.2656	80590	11508179	50516300
xlintstrfd	6.91786	2.83871	55.27958	14.7341	55.05883	16.0919	2.52	Scientific	0.192564	9.25948	10.1506	637225	30641060	33589806
xz	12.47186	165.904	19.04481	201.206	38.16606	442.429	122.79	Compression	33.5118	61.4542	250.13	110895605	203361402	827719243
xlintsts	0	0	0	0	0	0	7.88	Scientific	0	0	0	0	0	0
rsa	25.20674	0.982503	28.37400	1.09783	44.67524	5.40625	1.19	Encryption	0.29886	0.398462	3.8396	988974	1318573	12705819
xlintstzc	0.45077	3.45318	65.01240	8.67099	65.96053	8.87221	3.4	Scientific	0.0178991	3.99262	4.10318	59231	13212190	13578058
xeigtsts	11.23470	12.7019	51.98438	57.5048	52.12295	69.1639	10	Scientific	1.94289	36.0616	45.7432	6429313	119333422	151371255
ruby	27.45117	773.276	68.23405	452.397	74.50570	1457.51	334.59	Compilation	339.455	246.568	1081.97	1123308521	815933235	3580404496
ecdsa	0.59583	1.51335	30.36095	3.71921	48.78827	34.6543	3	Encryption	0.00970187	1.81028	26.748	32105	5990493	88513145
sha256	0.04167	0.023996	70.07435	0.035909	70.97978	0.035906	0.02	Encryption	1.81315	0.00944773	0.00944773	6	31264	31264
x264	4.63224	24.8359	32.79129	54.8662	40.19601	81.4002	21.83	Multimedia	1.69548	26.8859	48.9038	5610615	88969491	161830294
bn	17.28501	1.41102	42.44050	2.74798	49.55818	13.3332	1.95	Encryption	0.189999	1.25126	9.52644	628735	4140618	31524457
tcc	1.65262	1.04773	1.94112	1.04981	19.02888	1.59389	0.78	Compilation	0.0263847	0.0311022	0.465536	87311	102922	1540529
sdcc	4.60849	37.174	13.07639	45.065	27.37951	67.1632	33.93	Compilation	2.79976	9.40342	26.3489	9264838	31117361	87192550
dsa	14.77719	0.06575	32.38253	0.134869	45.26073	0.411646	0.12	Encryption	0.00656452	0.0601447	0.286302	21723	199028	947418
avconv	32.76636	391.598	45.82239	954.058	50.47306	2241.53	158.45	Multimedia	185.103	646.065	1707.72	612533880	2137927581	5651112367
mcrypt-aes	0.98847	0.000607	1.03493	0.000773	4.80864	0.001019	0	Encryption	2.71973	1.02745	6.31581	9	34	209
crafty	32.66182	149.382	35.68458	180.538	49.10960	762.656	49.67	Simulation	78.253	104.134	551.103	258951191	344593859	1823685121
cast	23.13607	1.82191	23.68817	1.83288	52.31559	2.55086	2.22	Encryption	0.604385	0.604385	1.20877	2000003	2000003	4000006
sqlite3	3.37639	209.77	10.54960	253.088	42.85096	1222.55	133.74	Database	10.3467	42.3868	826.465	34238968	140264495	2734900865
7za	17.11083	87.6771	17.19431	86.7941	36.24539	182.444	58.49	Compression	22.1783	22.1784	96.3277	73391561	73391595	318763285
lulesh	19.81049	358.94	20.87439	360.156	34.13904	562.886	221.18	Simulation	82.3364	82.3397	247.041	272463799	272474936	817496596
lammps	23.66195	571.567	41.87895	1578.11	49.63017	2737.59	297.26	Simulation	212.683	1007.1	1945.2	703800109	3332655138	6436962735
bzip2	5.07504	18.0003	17.80989	23.3612	48.40733	149.861	16.43	Compression	1.25096	5.54803	104.472	4139635	18359303	345715359