HomePhabricator

[ScheduleDAGInstrs] Compute topological ordering on demand.

Authored by fhahn on May 21 2019, 6:04 AM.

Description

[ScheduleDAGInstrs] Compute topological ordering on demand.

In most cases, the topological ordering does not get changed in
ScheduleDAGInstrs. We can compute the ordering on demand, similar to
D60125.

This drastically cuts down the number of times we need to compute the
topological ordering, e.g. for SPEC2006, SPEC2k and MultiSource, we get
the following stats for -O3 -flto on X86 (showing the top reductions,
with small absolute values filtered). The smallest reduction is -50%.

Slightly positive impact on compile-time (-0.1 % geomean speedup for
test-suite + SPEC & co, with -O1 on X86)

Tests: 243
Metric: pre-RA-sched.NumTopoInits

Program base patch diff
test-suite...ngs-C/fixoutput/fixoutput.test 115.00 3.00 -97.4%
test-suite...ks/Prolangs-C/cdecl/cdecl.test 957.00 26.00 -97.3%
test-suite...math/automotive-basicmath.test 107.00 3.00 -97.2%
test-suite...rolangs-C++/deriv2/deriv2.test 144.00 6.00 -95.8%
test-suite...lowfish/security-blowfish.test 410.00 18.00 -95.6%
test-suite...frame_layout/frame_layout.test 441.00 23.00 -94.8%
test-suite...rolangs-C++/employ/employ.test 159.00 11.00 -93.1%
test-suite...s/Ptrdist/anagram/anagram.test 157.00 11.00 -93.0%
test-suite...s-C/unix-smail/unix-smail.test 829.00 59.00 -92.9%
test-suite...chmarks/Olden/power/power.test 154.00 11.00 -92.9%
test-suite...T95/147.vortex/147.vortex.test 19876.00 1434.00 -92.8%
test-suite...000/255.vortex/255.vortex.test 19881.00 1435.00 -92.8%
test-suite...ce/Applications/Burg/burg.test 2203.00 168.00 -92.4%
test-suite...urce/Applications/hbd/hbd.test 1067.00 85.00 -92.0%
test-suite...ternal/HMMER/hmmcalibrate.test 3145.00 251.00 -92.0%
test-suite.../Applications/spiff/spiff.test 1037.00 84.00 -91.9%
test-suite...SPEC/CINT95/130.li/130.li.test 5913.00 487.00 -91.8%
test-suite.../CINT95/134.perl/134.perl.test 12532.00 1041.00 -91.7%
test-suite...ce/Benchmarks/Olden/bh/bh.test 220.00 19.00 -91.4%
test-suite :: External/Nurbs/nurbs.test 2304.00 206.00 -91.1%
test-suite...arks/VersaBench/dbms/dbms.test 773.00 75.00 -90.3%
test-suite...ce/Applications/siod/siod.test 9043.00 878.00 -90.3%
test-suite...pplications/treecc/treecc.test 4510.00 438.00 -90.3%
test-suite...T2006/456.hmmer/456.hmmer.test 7093.00 697.00 -90.2%
test-suite...s-C/Pathfinder/PathFinder.test 882.00 87.00 -90.1%
test-suite.../CINT2000/176.gcc/176.gcc.test 64978.00 6721.00 -89.7%
test-suite...cations/hexxagon/hexxagon.test 657.00 69.00 -89.5%
test-suite...fice-ispell/office-ispell.test 2712.00 285.00 -89.5%
test-suite.../CINT2006/403.gcc/403.gcc.test 139613.00 14992.00 -89.3%
test-suite...lications/ClamAV/clamscan.test 25880.00 2785.00 -89.2%

Reviewers: MatzeB, atrick, efriedma, niravd

Reviewed By: efriedma

Differential Revision: https://reviews.llvm.org/D60839

llvm-svn: 361253