tree 59ebede4c41e879b55da01c4e409cf6a1335d8e5
parent 488f64fa631eb482b98cee2b468c4f03e0a50dfe
author Florian Hahn <flo@fhahn.com> 1555513529 +0000
committer Florian Hahn <flo@fhahn.com> 1555513529 +0000

[ScheduleDAGRRList] Recompute topological ordering on demand.

Currently there is a single point in ScheduleDAGRRList, where we
actually query the topological order (besides init code). Currently we
are recomputing the order after adding a node (which does not have
predecessors) and then we add predecessors edge-by-edge.

We can avoid adding edges one-by-one after we added a new node. In that case, we can
just rebuild the order from scratch after adding the edges to the DAG
and avoid all the updates to the ordering.

Also, we can delay updating the DAG until we query the DAG, if we keep a
list of added edges. Depending on the number of updates, we can either
apply them when needed or recompute the order from scratch.

This brings down the geomean compile time for of CTMark with -O1 down 0.3% on X86,
with no regressions.

Reviewers: MatzeB, atrick, efriedma, niravd, paquette

Reviewed By: efriedma

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

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@358583 91177308-0d34-0410-b5e6-96231b3b80d8