[ScheduleDAGInstrs] Compute topological ordering on demand.

[fhahn]

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%

[tstellar]

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]

llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h

349 ↗

(On Diff #195634)

Is this helper actually used anywhere?

[fhahn]

Remove unused MarkDirty.

[fhahn]

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]

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)

[efriedma]

LGTM

[fhahn]

Thanks Eli!

llvm/lib/CodeGen/ScheduleDAGInstrs.cpp

void ScheduleDAGInstrs::buildSchedGraph(AliasAnalysis *AA,
   if (DbgMI)
     FirstDbgValue = DbgMI;
 
   Defs.clear();
   Uses.clear();
   CurrentVRegDefs.clear();
   CurrentVRegUses.clear();
 
-  Topo.InitDAGTopologicalSorting();
+  Topo.MarkDirty();
 }
 
 raw_ostream &llvm::operator<<(raw_ostream &OS, const PseudoSourceValue* PSV) {
   PSV->printCustom(OS);
   return OS;
 }
 
 void ScheduleDAGInstrs::Value2SUsMap::dump() {

 }
 
 bool ScheduleDAGInstrs::addEdge(SUnit *SuccSU, const SDep &PredDep) {
   if (SuccSU != &ExitSU) {
     // Do not use WillCreateCycle, it assumes SD scheduling.
     // If Pred is reachable from Succ, then the edge creates a cycle.
     if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
       return false;
-    Topo.AddPred(SuccSU, PredDep.getSUnit());
+    Topo.AddPredQueued(SuccSU, PredDep.getSUnit());
   }
   SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial());
   // Return true regardless of whether a new edge needed to be inserted.
   return true;
 }
 
 //===----------------------------------------------------------------------===//
 // SchedDFSResult Implementation