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
first_target(GrRenderTask * task)16 static GrSurfaceProxy* first_target(GrRenderTask* task) { return task->target(0); }
17
18 #ifdef SK_DEBUG
describe_task(GrRenderTask * t)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
describe_tasks(SkSpan<const sk_sp<GrRenderTask>> collection)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
describe_tasks(const SkTInternalLList<GrRenderTask> & collection)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
validate(SkSpan<const sk_sp<GrRenderTask>> input,const SkTInternalLList<GrRenderTask> & llist)43 static 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.
depends_on(GrRenderTask * depender,GrRenderTask * dependee)66 static 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 for (GrRenderTask* t : depender->dependencies()) {
81 if (dependee == t) {
82 CLUSTER_DEBUGF("Cluster: Bail, %s depends on %s.\n",
83 describe_task(depender).c_str(),
84 describe_task(dependee).c_str());
85 return true;
86 }
87 }
88 return false;
89 }
90
91 // Returns whether reordering occurred.
task_cluster_visit(GrRenderTask * task,SkTInternalLList<GrRenderTask> * llist,SkTHashMap<GrSurfaceProxy *,GrRenderTask * > * lastTaskMap)92 static bool task_cluster_visit(GrRenderTask* task, SkTInternalLList<GrRenderTask>* llist,
93 SkTHashMap<GrSurfaceProxy*, GrRenderTask*>* lastTaskMap) {
94 CLUSTER_DEBUGF("Cluster: ***Step***\nLooking at %s\n",
95 describe_task(task).c_str());
96 if (task->numTargets() != 1) {
97 CLUSTER_DEBUGF("Cluster: %d targets. Emitting barriers.\n", task->numTargets());
98 // Tasks with 0 or multiple targets are treated as full barriers
99 // for all their targets.
100 for (int j = 0; j < task->numTargets(); j++) {
101 if (lastTaskMap->find(task->target(0))) {
102 lastTaskMap->remove(task->target(0));
103 }
104 }
105 return false;
106 }
107
108 GrSurfaceProxy* target = first_target(task);
109 GrRenderTask* clusterTail = (lastTaskMap->find(target) ? *lastTaskMap->find(target) : nullptr);
110 lastTaskMap->set(target, task);
111
112 if (!clusterTail) {
113 CLUSTER_DEBUGF("Cluster: Bail, no cluster to extend.\n");
114 return false;
115 }
116
117 CLUSTER_DEBUGF("Cluster: clusterTail is %s.\n", describe_task(clusterTail).c_str());
118
119 if (clusterTail == llist->tail()) {
120 CLUSTER_DEBUGF("Cluster: Bail, cluster is already tail.\n");
121 return false;
122 }
123 GrRenderTask* movedHead = clusterTail->fNext;
124
125 // Now, let's refer to the "cluster" as the chain of tasks with the same target, that we're
126 // hoping to extend by reordering. Let "moved tasks" be the ones we want to move to extend the
127 // cluster.
128 GrRenderTask* clusterHead = clusterTail;
129 while (clusterHead->fPrev
130 && 1 == clusterHead->fPrev->numTargets()
131 && target == first_target(clusterHead->fPrev)) {
132 clusterHead = clusterHead->fPrev;
133 }
134
135 // We can't reorder if any moved task depends on anything in the cluster.
136 // Time complexity here is high, but making a hash set is worse in profiling.
137 for (GrRenderTask* moved = movedHead; moved; moved = moved->fNext) {
138 for (GrRenderTask* passed = clusterHead; passed != movedHead; passed = passed->fNext) {
139 if (depends_on(moved, passed)) {
140 return false;
141 }
142 }
143 }
144
145 // Grab the moved tasks and pull them before clusterHead.
146 for (GrRenderTask* moved = movedHead; moved;) {
147 CLUSTER_DEBUGF("Cluster: Reorder %s behind %s.\n",
148 describe_task(moved).c_str(),
149 describe_task(clusterHead).c_str());
150 // Be careful to save fNext before each move.
151 GrRenderTask* nextMoved = moved->fNext;
152 llist->remove(moved);
153 llist->addBefore(moved, clusterHead);
154 moved = nextMoved;
155 }
156 return true;
157 }
158
GrClusterRenderTasks(SkSpan<const sk_sp<GrRenderTask>> input,SkTInternalLList<GrRenderTask> * llist)159 bool GrClusterRenderTasks(SkSpan<const sk_sp<GrRenderTask>> input,
160 SkTInternalLList<GrRenderTask>* llist) {
161 SkASSERT(llist->isEmpty());
162
163 if (input.size() < 3) {
164 return false;
165 }
166
167 CLUSTER_DEBUGF("Cluster: Original order is %s\n", describe_tasks(input).c_str());
168
169 SkTHashMap<GrSurfaceProxy*, GrRenderTask*> lastTaskMap;
170 bool didReorder = false;
171 for (const auto& t : input) {
172 didReorder |= task_cluster_visit(t.get(), llist, &lastTaskMap);
173 llist->addToTail(t.get());
174 CLUSTER_DEBUGF("Cluster: Output order is now: %s\n", describe_tasks(*llist).c_str());
175 }
176
177 #ifdef SK_DEBUG
178 if (didReorder) {
179 validate(input, *llist);
180 }
181 #endif
182
183 return didReorder;
184 }
185
186 #undef CLUSTER_DEBUGF
187