Page MenuHomePhabricator

[ScheduleDAGInstrs] Compute topological ordering on demand.
ClosedPublic

Authored by fhahn on Apr 17 2019, 2:51 PM.

Details

Summary

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%.

I'll provide compile-time numbers after the weekend.

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

Program rr-lazy mi-lazy 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%

Diff Detail

Repository
rL LLVM

Event Timeline

fhahn created this revision.Apr 17 2019, 2:51 PM

Thanks for working on this. Here are some unscientific benchmarks from a pathological case on AMDGPU:

before rL358583:
real 0m2.134s
user 0m2.081s
sys 0m0.053s

rL358583:
real 0m1.858s
user 0m1.810s
sys 0m0.048s

D60839:
real 0m1.798s
user 0m1.742s
sys 0m0.057s

And prior to rL340346 this program took 7.5s to compile, and it's relatively small (2943 IR instructions).

efriedma added inline comments.Apr 19 2019, 2:45 PM
llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h
349 ↗(On Diff #195634)

Is this helper actually used anywhere?

fhahn updated this revision to Diff 200181.May 19 2019, 8:57 AM
fhahn marked 2 inline comments as done.

Remove unused MarkDirty.

fhahn added inline comments.May 19 2019, 8:59 AM
llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h
349 ↗(On Diff #195634)

No, it was is left over from an earlier version. I've removed it, thanks!

fhahn added a comment.May 19 2019, 9:01 AM

I've verified this does not change CodeGen for the test-suite + various external suites. Slightly positive impact on compile-time (-0.1 % geomean speedup for test-suite + SPEC & co, with -O1 on X86)

This revision is now accepted and ready to land.May 20 2019, 12:31 PM
fhahn added a comment.May 21 2019, 6:02 AM

Thanks Eli!

This revision was automatically updated to reflect the committed changes.