[ScheduleDAGRRList] Recompute topological ordering on demand.
authorFlorian Hahn <flo@fhahn.com>
Wed, 17 Apr 2019 15:05:29 +0000 (15:05 +0000)
committerFlorian Hahn <flo@fhahn.com>
Wed, 17 Apr 2019 15:05:29 +0000 (15:05 +0000)
commit258a425c69f0f611ae237ad507252ad18048d2ab
tree1a537247edbd121692a69a5badbb5032414fab00
parent491ff04a49a6cfae994dc8cc15d0d70ce39a95d3
[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

llvm-svn: 358583
llvm/include/llvm/CodeGen/ScheduleDAG.h
llvm/lib/CodeGen/ScheduleDAG.cpp
llvm/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp