OSDN Git Service

[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)
commit94ebdffbc8ca32a6bc93626b99db8e20323118b1
tree59ebede4c41e879b55da01c4e409cf6a1335d8e5
parent488f64fa631eb482b98cee2b468c4f03e0a50dfe
[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
include/llvm/CodeGen/ScheduleDAG.h
lib/CodeGen/ScheduleDAG.cpp
lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp