1//
2// Copyright (c) 2002-2012 The ANGLE Project Authors. All rights reserved.
3// Use of this source code is governed by a BSD-style license that can be
4// found in the LICENSE file.
5//
6// Check whether variables fit within packing limits according to the packing rules from the GLSL ES
7// 1.00.17 spec, Appendix A, section 7.
8
9#include <algorithm>
10
11#include "angle_gl.h"
12
13#include "common/utilities.h"
14#include "compiler/translator/VariablePacker.h"
15
16namespace sh
17{
18
19namespace
20{
21
22// Expand the variable so that struct variables are split into their individual fields.
23// Will not set the mappedName or staticUse fields on the expanded variables.
24void ExpandVariable(const ShaderVariable &variable,
25 const std::string &name,
26 std::vector<ShaderVariable> *expanded);
27
28void ExpandStructVariable(const ShaderVariable &variable,
29 const std::string &name,
30 std::vector<ShaderVariable> *expanded)
31{
32 ASSERT(variable.isStruct());
33
34 const std::vector<ShaderVariable> &fields = variable.fields;
35
36 for (size_t fieldIndex = 0; fieldIndex < fields.size(); fieldIndex++)
37 {
38 const ShaderVariable &field = fields[fieldIndex];
39 ExpandVariable(field, name + "." + field.name, expanded);
40 }
41}
42
43void ExpandStructArrayVariable(const ShaderVariable &variable,
44 unsigned int arrayNestingIndex,
45 const std::string &name,
46 std::vector<ShaderVariable> *expanded)
47{
48 // Nested arrays are processed starting from outermost (arrayNestingIndex 0u) and ending at the
49 // innermost.
50 const unsigned int currentArraySize = variable.getNestedArraySize(arrayNestingIndex);
51 for (unsigned int arrayElement = 0u; arrayElement < currentArraySize; ++arrayElement)
52 {
53 const std::string elementName = name + ArrayString(arrayElement);
54 if (arrayNestingIndex + 1u < variable.arraySizes.size())
55 {
56 ExpandStructArrayVariable(variable, arrayNestingIndex + 1u, elementName, expanded);
57 }
58 else
59 {
60 ExpandStructVariable(variable, elementName, expanded);
61 }
62 }
63}
64
65void ExpandVariable(const ShaderVariable &variable,
66 const std::string &name,
67 std::vector<ShaderVariable> *expanded)
68{
69 if (variable.isStruct())
70 {
71 if (variable.isArray())
72 {
73 ExpandStructArrayVariable(variable, 0u, name, expanded);
74 }
75 else
76 {
77 ExpandStructVariable(variable, name, expanded);
78 }
79 }
80 else
81 {
82 ShaderVariable expandedVar = variable;
83 expandedVar.name = name;
84
85 expanded->push_back(expandedVar);
86 }
87}
88
89int GetVariablePackingRows(const ShaderVariable &variable)
90{
91 return GetTypePackingRows(variable.type) * variable.getArraySizeProduct();
92}
93
94class VariablePacker
95{
96 public:
97 bool checkExpandedVariablesWithinPackingLimits(unsigned int maxVectors,
98 std::vector<sh::ShaderVariable> *variables);
99
100 private:
101 static const int kNumColumns = 4;
102 static const unsigned kColumnMask = (1 << kNumColumns) - 1;
103
104 unsigned makeColumnFlags(int column, int numComponentsPerRow);
105 void fillColumns(int topRow, int numRows, int column, int numComponentsPerRow);
106 bool searchColumn(int column, int numRows, int *destRow, int *destSize);
107
108 int topNonFullRow_;
109 int bottomNonFullRow_;
110 int maxRows_;
111 std::vector<unsigned> rows_;
112};
113
114struct TVariableInfoComparer
115{
116 bool operator()(const sh::ShaderVariable &lhs, const sh::ShaderVariable &rhs) const
117 {
118 int lhsSortOrder = gl::VariableSortOrder(lhs.type);
119 int rhsSortOrder = gl::VariableSortOrder(rhs.type);
120 if (lhsSortOrder != rhsSortOrder)
121 {
122 return lhsSortOrder < rhsSortOrder;
123 }
124 // Sort by largest first.
125 return lhs.getArraySizeProduct() > rhs.getArraySizeProduct();
126 }
127};
128
129unsigned VariablePacker::makeColumnFlags(int column, int numComponentsPerRow)
130{
131 return ((kColumnMask << (kNumColumns - numComponentsPerRow)) & kColumnMask) >> column;
132}
133
134void VariablePacker::fillColumns(int topRow, int numRows, int column, int numComponentsPerRow)
135{
136 unsigned columnFlags = makeColumnFlags(column, numComponentsPerRow);
137 for (int r = 0; r < numRows; ++r)
138 {
139 int row = topRow + r;
140 ASSERT((rows_[row] & columnFlags) == 0);
141 rows_[row] |= columnFlags;
142 }
143}
144
145bool VariablePacker::searchColumn(int column, int numRows, int *destRow, int *destSize)
146{
147 ASSERT(destRow);
148
149 for (; topNonFullRow_ < maxRows_ && rows_[topNonFullRow_] == kColumnMask; ++topNonFullRow_)
150 {
151 }
152
153 for (; bottomNonFullRow_ >= 0 && rows_[bottomNonFullRow_] == kColumnMask; --bottomNonFullRow_)
154 {
155 }
156
157 if (bottomNonFullRow_ - topNonFullRow_ + 1 < numRows)
158 {
159 return false;
160 }
161
162 unsigned columnFlags = makeColumnFlags(column, 1);
163 int topGoodRow = 0;
164 int smallestGoodTop = -1;
165 int smallestGoodSize = maxRows_ + 1;
166 int bottomRow = bottomNonFullRow_ + 1;
167 bool found = false;
168 for (int row = topNonFullRow_; row <= bottomRow; ++row)
169 {
170 bool rowEmpty = row < bottomRow ? ((rows_[row] & columnFlags) == 0) : false;
171 if (rowEmpty)
172 {
173 if (!found)
174 {
175 topGoodRow = row;
176 found = true;
177 }
178 }
179 else
180 {
181 if (found)
182 {
183 int size = row - topGoodRow;
184 if (size >= numRows && size < smallestGoodSize)
185 {
186 smallestGoodSize = size;
187 smallestGoodTop = topGoodRow;
188 }
189 }
190 found = false;
191 }
192 }
193 if (smallestGoodTop < 0)
194 {
195 return false;
196 }
197
198 *destRow = smallestGoodTop;
199 if (destSize)
200 {
201 *destSize = smallestGoodSize;
202 }
203 return true;
204}
205
206bool VariablePacker::checkExpandedVariablesWithinPackingLimits(
207 unsigned int maxVectors,
208 std::vector<sh::ShaderVariable> *variables)
209{
210 ASSERT(maxVectors > 0);
211 maxRows_ = maxVectors;
212 topNonFullRow_ = 0;
213 bottomNonFullRow_ = maxRows_ - 1;
214
215 // Check whether each variable fits in the available vectors.
216 for (const sh::ShaderVariable &variable : *variables)
217 {
218 // Structs should have been expanded before reaching here.
219 ASSERT(!variable.isStruct());
220 if (variable.getArraySizeProduct() > maxVectors / GetTypePackingRows(variable.type))
221 {
222 return false;
223 }
224 }
225
226 // As per GLSL 1.017 Appendix A, Section 7 variables are packed in specific
227 // order by type, then by size of array, largest first.
228 std::sort(variables->begin(), variables->end(), TVariableInfoComparer());
229 rows_.clear();
230 rows_.resize(maxVectors, 0);
231
232 // Packs the 4 column variables.
233 size_t ii = 0;
234 for (; ii < variables->size(); ++ii)
235 {
236 const sh::ShaderVariable &variable = (*variables)[ii];
237 if (GetTypePackingComponentsPerRow(variable.type) != 4)
238 {
239 break;
240 }
241 topNonFullRow_ += GetVariablePackingRows(variable);
242 }
243
244 if (topNonFullRow_ > maxRows_)
245 {
246 return false;
247 }
248
249 // Packs the 3 column variables.
250 int num3ColumnRows = 0;
251 for (; ii < variables->size(); ++ii)
252 {
253 const sh::ShaderVariable &variable = (*variables)[ii];
254 if (GetTypePackingComponentsPerRow(variable.type) != 3)
255 {
256 break;
257 }
258 num3ColumnRows += GetVariablePackingRows(variable);
259 }
260
261 if (topNonFullRow_ + num3ColumnRows > maxRows_)
262 {
263 return false;
264 }
265
266 fillColumns(topNonFullRow_, num3ColumnRows, 0, 3);
267
268 // Packs the 2 column variables.
269 int top2ColumnRow = topNonFullRow_ + num3ColumnRows;
270 int twoColumnRowsAvailable = maxRows_ - top2ColumnRow;
271 int rowsAvailableInColumns01 = twoColumnRowsAvailable;
272 int rowsAvailableInColumns23 = twoColumnRowsAvailable;
273 for (; ii < variables->size(); ++ii)
274 {
275 const sh::ShaderVariable &variable = (*variables)[ii];
276 if (GetTypePackingComponentsPerRow(variable.type) != 2)
277 {
278 break;
279 }
280 int numRows = GetVariablePackingRows(variable);
281 if (numRows <= rowsAvailableInColumns01)
282 {
283 rowsAvailableInColumns01 -= numRows;
284 }
285 else if (numRows <= rowsAvailableInColumns23)
286 {
287 rowsAvailableInColumns23 -= numRows;
288 }
289 else
290 {
291 return false;
292 }
293 }
294
295 int numRowsUsedInColumns01 = twoColumnRowsAvailable - rowsAvailableInColumns01;
296 int numRowsUsedInColumns23 = twoColumnRowsAvailable - rowsAvailableInColumns23;
297 fillColumns(top2ColumnRow, numRowsUsedInColumns01, 0, 2);
298 fillColumns(maxRows_ - numRowsUsedInColumns23, numRowsUsedInColumns23, 2, 2);
299
300 // Packs the 1 column variables.
301 for (; ii < variables->size(); ++ii)
302 {
303 const sh::ShaderVariable &variable = (*variables)[ii];
304 ASSERT(1 == GetTypePackingComponentsPerRow(variable.type));
305 int numRows = GetVariablePackingRows(variable);
306 int smallestColumn = -1;
307 int smallestSize = maxRows_ + 1;
308 int topRow = -1;
309 for (int column = 0; column < kNumColumns; ++column)
310 {
311 int row = 0;
312 int size = 0;
313 if (searchColumn(column, numRows, &row, &size))
314 {
315 if (size < smallestSize)
316 {
317 smallestSize = size;
318 smallestColumn = column;
319 topRow = row;
320 }
321 }
322 }
323
324 if (smallestColumn < 0)
325 {
326 return false;
327 }
328
329 fillColumns(topRow, numRows, smallestColumn, 1);
330 }
331
332 ASSERT(variables->size() == ii);
333
334 return true;
335}
336
337} // anonymous namespace
338
339int GetTypePackingComponentsPerRow(sh::GLenum type)
340{
341 switch (type)
342 {
343 case GL_FLOAT_MAT4:
344 case GL_FLOAT_MAT2:
345 case GL_FLOAT_MAT2x4:
346 case GL_FLOAT_MAT3x4:
347 case GL_FLOAT_MAT4x2:
348 case GL_FLOAT_MAT4x3:
349 case GL_FLOAT_VEC4:
350 case GL_INT_VEC4:
351 case GL_BOOL_VEC4:
352 case GL_UNSIGNED_INT_VEC4:
353 return 4;
354 case GL_FLOAT_MAT3:
355 case GL_FLOAT_MAT2x3:
356 case GL_FLOAT_MAT3x2:
357 case GL_FLOAT_VEC3:
358 case GL_INT_VEC3:
359 case GL_BOOL_VEC3:
360 case GL_UNSIGNED_INT_VEC3:
361 return 3;
362 case GL_FLOAT_VEC2:
363 case GL_INT_VEC2:
364 case GL_BOOL_VEC2:
365 case GL_UNSIGNED_INT_VEC2:
366 return 2;
367 default:
368 ASSERT(gl::VariableComponentCount(type) == 1);
369 return 1;
370 }
371}
372
373int GetTypePackingRows(sh::GLenum type)
374{
375 switch (type)
376 {
377 case GL_FLOAT_MAT4:
378 case GL_FLOAT_MAT2x4:
379 case GL_FLOAT_MAT3x4:
380 case GL_FLOAT_MAT4x3:
381 case GL_FLOAT_MAT4x2:
382 return 4;
383 case GL_FLOAT_MAT3:
384 case GL_FLOAT_MAT2x3:
385 case GL_FLOAT_MAT3x2:
386 return 3;
387 case GL_FLOAT_MAT2:
388 return 2;
389 default:
390 ASSERT(gl::VariableRowCount(type) == 1);
391 return 1;
392 }
393}
394
395template <typename T>
396bool CheckVariablesInPackingLimits(unsigned int maxVectors, const std::vector<T> &variables)
397{
398 VariablePacker packer;
399 std::vector<sh::ShaderVariable> expandedVariables;
400 for (const ShaderVariable &variable : variables)
401 {
402 ExpandVariable(variable, variable.name, &expandedVariables);
403 }
404 return packer.checkExpandedVariablesWithinPackingLimits(maxVectors, &expandedVariables);
405}
406
407template bool CheckVariablesInPackingLimits<ShaderVariable>(
408 unsigned int maxVectors,
409 const std::vector<ShaderVariable> &variables);
410template bool CheckVariablesInPackingLimits<Uniform>(unsigned int maxVectors,
411 const std::vector<Uniform> &variables);
412
413} // namespace sh
414