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 "src/core/SkTHash.h"
11 #include "src/gpu/ganesh/GrRenderTask.h"
12
13 using namespace skia_private;
14
15 // Uncomment to get lots of logging.
16 #define CLUSTER_DEBUGF(...) //SkDebugf(__VA_ARGS__)
17
first_target(GrRenderTask * task)18 static GrSurfaceProxy* first_target(GrRenderTask* task) { return task->target(0); }
19
20 #ifdef SK_DEBUG
describe_task(GrRenderTask * t)21 [[maybe_unused]] static SkString describe_task(GrRenderTask* t) {
22 if (GrSurfaceProxy* target = first_target(t)) {
23 return SkStringPrintf("%s(%u)", target->getDebugName().c_str(), t->uniqueID());
24 } else {
25 return SkStringPrintf("%u", t->uniqueID());
26 }
27 }
28
describe_tasks(SkSpan<const sk_sp<GrRenderTask>> collection)29 [[maybe_unused]] static SkString describe_tasks(SkSpan<const sk_sp<GrRenderTask>> collection) {
30 SkString s;
31 for (const sk_sp<GrRenderTask>& t : collection) {
32 s.appendf("%s ", describe_task(t.get()).c_str());
33 }
34 return s;
35 }
36
describe_tasks(const SkTInternalLList<GrRenderTask> & collection)37 [[maybe_unused]] static SkString describe_tasks(const SkTInternalLList<GrRenderTask>& collection) {
38 SkString s;
39 for (GrRenderTask* t : collection) {
40 s.appendf("%s ", describe_task(t).c_str());
41 }
42 return s;
43 }
44
validate(SkSpan<const sk_sp<GrRenderTask>> input,const SkTInternalLList<GrRenderTask> & llist)45 static void validate(SkSpan<const sk_sp<GrRenderTask>> input,
46 const SkTInternalLList<GrRenderTask>& llist) {
47 // Check that we didn't break dependencies.
48 THashSet<GrRenderTask*> seen;
49 for (GrRenderTask* t : llist) {
50 seen.add(t);
51 for (GrRenderTask* dep : t->dependencies()) {
52 SkASSERTF(seen.contains(dep),
53 "%s came before dependency %s",
54 describe_task(t).c_str(),
55 describe_task(dep).c_str());
56 }
57 }
58 // Check that llist has the same entries as the input.
59 for (const auto& orig : input) {
60 seen.remove(orig.get());
61 }
62 SkASSERT(seen.empty());
63 }
64
65 #endif // SK_DEBUG
66
67 // Returns whether `dependee` is a formal dependent or if it uses a surface `depender` targets.
depends_on(GrRenderTask * depender,GrRenderTask * dependee)68 static bool depends_on(GrRenderTask* depender, GrRenderTask* dependee) {
69 // Check if depender writes to something dependee reads.
70 // TODO: Establish real DAG dependencies for this during recording? E.g. when a task adds a
71 // target, search backward for the last task that uses the target and add a dep.
72 for (int i = 0; i < depender->numTargets(); i++) {
73 if (dependee->isUsed(depender->target(i))) {
74 CLUSTER_DEBUGF("Cluster: Bail, %s can't write before %s reads from %s.\n",
75 describe_task(depender).c_str(),
76 describe_task(dependee).c_str(),
77 depender->target(i)->getDebugName().c_str());
78 return true;
79 }
80 }
81 // Check for a formal dependency.
82 if (depender->dependsOn(dependee)) {
83 CLUSTER_DEBUGF("Cluster: Bail, %s depends on %s.\n",
84 describe_task(depender).c_str(),
85 describe_task(dependee).c_str());
86 return true;
87 }
88 return false;
89 }
90
91 // Returns whether reordering occurred.
task_cluster_visit(GrRenderTask * task,SkTInternalLList<GrRenderTask> * llist,THashMap<GrSurfaceProxy *,GrRenderTask * > * lastTaskMap)92 static bool task_cluster_visit(GrRenderTask* task, SkTInternalLList<GrRenderTask>* llist,
93 THashMap<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 for (const auto& t : input) {
165 llist->addToTail(t.get());
166 }
167 return false;
168 }
169
170 CLUSTER_DEBUGF("Cluster: Original order is %s\n", describe_tasks(input).c_str());
171
172 THashMap<GrSurfaceProxy*, GrRenderTask*> lastTaskMap;
173 bool didReorder = false;
174 for (const auto& t : input) {
175 didReorder |= task_cluster_visit(t.get(), llist, &lastTaskMap);
176 llist->addToTail(t.get());
177 CLUSTER_DEBUGF("Cluster: Output order is now: %s\n", describe_tasks(*llist).c_str());
178 }
179
180 #ifdef SK_DEBUG
181 if (didReorder) {
182 validate(input, *llist);
183 }
184 #endif
185
186 return didReorder;
187 }
188
189 #undef CLUSTER_DEBUGF
190