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