1/*
2 * Copyright 2021 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "src/gpu/GrRenderTaskCluster.h"
9
10#include "include/private/SkTHash.h"
11#include "src/gpu/GrRenderTask.h"
12
13// Uncomment to get lots of logging.
14#define CLUSTER_DEBUGF(...) //SkDebugf(__VA_ARGS__)
15
16static GrSurfaceProxy* first_target(GrRenderTask* task) { return task->target(0); }
17
18#ifdef SK_DEBUG
19[[maybe_unused]] static SkString describe_task(GrRenderTask* t) {
20    if (GrSurfaceProxy* target = first_target(t)) {
21        return SkStringPrintf("%s(%d)", target->getDebugName().c_str(), t->uniqueID());
22    } else {
23        return SkStringPrintf("%d", t->uniqueID());
24    }
25}
26
27[[maybe_unused]] static SkString describe_tasks(SkSpan<const sk_sp<GrRenderTask>> collection) {
28    SkString s;
29    for (const sk_sp<GrRenderTask>& t : collection) {
30        s.appendf("%s ", describe_task(t.get()).c_str());
31    }
32    return s;
33}
34
35[[maybe_unused]] static SkString describe_tasks(const SkTInternalLList<GrRenderTask>& collection) {
36    SkString s;
37    for (GrRenderTask* t : collection) {
38        s.appendf("%s ", describe_task(t).c_str());
39    }
40    return s;
41}
42
43static void validate(SkSpan<const sk_sp<GrRenderTask>> input,
44                     const SkTInternalLList<GrRenderTask>& llist) {
45    // Check that we didn't break dependencies.
46    SkTHashSet<GrRenderTask*> seen;
47    for (GrRenderTask* t : llist) {
48        seen.add(t);
49        for (GrRenderTask* dep : t->dependencies()) {
50            SkASSERTF(seen.contains(dep),
51                      "%s came before dependency %s",
52                      describe_task(t).c_str(),
53                      describe_task(dep).c_str());
54        }
55    }
56    // Check that llist has the same entries as the input.
57    for (const auto& orig : input) {
58        seen.remove(orig.get());
59    }
60    SkASSERT(seen.empty());
61}
62
63#endif  // SK_DEBUG
64
65// Returns whether `dependee` is a formal dependent or if it uses a surface `depender` targets.
66static bool depends_on(GrRenderTask* depender, GrRenderTask* dependee) {
67    // Check if depender writes to something dependee reads.
68    // TODO: Establish real DAG dependencies for this during recording? E.g. when a task adds a
69    // target, search backward for the last task that uses the target and add a dep.
70    for (int i = 0; i < depender->numTargets(); i++) {
71        if (dependee->isUsed(depender->target(i))) {
72            CLUSTER_DEBUGF("Cluster: Bail, %s can't write before %s reads from %s.\n",
73                           describe_task(depender).c_str(),
74                           describe_task(dependee).c_str(),
75                           depender->target(i)->getDebugName().c_str());
76            return true;
77        }
78    }
79    // Check for a formal dependency.
80    if (depender->dependsOn(dependee)) {
81        CLUSTER_DEBUGF("Cluster: Bail, %s depends on %s.\n",
82                       describe_task(depender).c_str(),
83                       describe_task(dependee).c_str());
84        return true;
85    }
86    return false;
87}
88
89// Returns whether reordering occurred.
90static bool task_cluster_visit(GrRenderTask* task, SkTInternalLList<GrRenderTask>* llist,
91                               SkTHashMap<GrSurfaceProxy*, GrRenderTask*>* lastTaskMap) {
92    CLUSTER_DEBUGF("Cluster: ***Step***\nLooking at %s\n",
93                   describe_task(task).c_str());
94    if (task->numTargets() != 1) {
95        CLUSTER_DEBUGF("Cluster: %d targets. Emitting barriers.\n", task->numTargets());
96        // Tasks with 0 or multiple targets are treated as full barriers
97        // for all their targets.
98        for (int j = 0; j < task->numTargets(); j++) {
99            if (lastTaskMap->find(task->target(0))) {
100                lastTaskMap->remove(task->target(0));
101            }
102        }
103        return false;
104    }
105
106    GrSurfaceProxy* target = first_target(task);
107    GrRenderTask* clusterTail = (lastTaskMap->find(target) ? *lastTaskMap->find(target) : nullptr);
108    lastTaskMap->set(target, task);
109
110    if (!clusterTail) {
111        CLUSTER_DEBUGF("Cluster: Bail, no cluster to extend.\n");
112        return false;
113    }
114
115    CLUSTER_DEBUGF("Cluster: clusterTail is %s.\n", describe_task(clusterTail).c_str());
116
117    if (clusterTail == llist->tail()) {
118        CLUSTER_DEBUGF("Cluster: Bail, cluster is already tail.\n");
119        return false;
120    }
121    GrRenderTask* movedHead = clusterTail->fNext;
122
123    // Now, let's refer to the "cluster" as the chain of tasks with the same target, that we're
124    // hoping to extend by reordering. Let "moved tasks" be the ones we want to move to extend the
125    // cluster.
126    GrRenderTask* clusterHead = clusterTail;
127    while (clusterHead->fPrev
128           && 1 == clusterHead->fPrev->numTargets()
129           && target == first_target(clusterHead->fPrev)) {
130        clusterHead = clusterHead->fPrev;
131    }
132
133    // We can't reorder if any moved task depends on anything in the cluster.
134    // Time complexity here is high, but making a hash set is worse in profiling.
135    for (GrRenderTask* moved = movedHead; moved; moved = moved->fNext) {
136        for (GrRenderTask* passed = clusterHead; passed != movedHead; passed = passed->fNext) {
137            if (depends_on(moved, passed)) {
138                return false;
139            }
140        }
141    }
142
143    // Grab the moved tasks and pull them before clusterHead.
144    for (GrRenderTask* moved = movedHead; moved;) {
145        CLUSTER_DEBUGF("Cluster: Reorder %s behind %s.\n",
146                       describe_task(moved).c_str(),
147                       describe_task(clusterHead).c_str());
148        // Be careful to save fNext before each move.
149        GrRenderTask* nextMoved = moved->fNext;
150        llist->remove(moved);
151        llist->addBefore(moved, clusterHead);
152        moved = nextMoved;
153    }
154    return true;
155}
156
157bool GrClusterRenderTasks(SkSpan<const sk_sp<GrRenderTask>> input,
158                          SkTInternalLList<GrRenderTask>* llist) {
159    SkASSERT(llist->isEmpty());
160
161    if (input.size() < 3) {
162        return false;
163    }
164
165    CLUSTER_DEBUGF("Cluster: Original order is %s\n", describe_tasks(input).c_str());
166
167    SkTHashMap<GrSurfaceProxy*, GrRenderTask*> lastTaskMap;
168    bool didReorder = false;
169    for (const auto& t : input) {
170        didReorder |= task_cluster_visit(t.get(), llist, &lastTaskMap);
171        llist->addToTail(t.get());
172        CLUSTER_DEBUGF("Cluster: Output order is now: %s\n", describe_tasks(*llist).c_str());
173    }
174
175#ifdef SK_DEBUG
176    if (didReorder) {
177        validate(input, *llist);
178    }
179#endif
180
181    return didReorder;
182}
183
184#undef CLUSTER_DEBUGF
185