Home | History | Annotate | Download | only in translator 
      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 #include "compiler/translator/VariablePacker.h"
      7 
      8 #include <algorithm>
      9 #include "compiler/translator/ShHandle.h"
     10 
     11 namespace {
     12 int GetSortOrder(ShDataType type)
     13 {
     14     switch (type) {
     15         case SH_FLOAT_MAT4:
     16         case SH_FLOAT_MAT2x4:
     17         case SH_FLOAT_MAT3x4:
     18         case SH_FLOAT_MAT4x2:
     19         case SH_FLOAT_MAT4x3:
     20             return 0;
     21         case SH_FLOAT_MAT2:
     22             return 1;
     23         case SH_FLOAT_VEC4:
     24         case SH_INT_VEC4:
     25         case SH_BOOL_VEC4:
     26             return 2;
     27         case SH_FLOAT_MAT3:
     28         case SH_FLOAT_MAT2x3:
     29         case SH_FLOAT_MAT3x2:
     30             return 3;
     31         case SH_FLOAT_VEC3:
     32         case SH_INT_VEC3:
     33         case SH_BOOL_VEC3:
     34             return 4;
     35         case SH_FLOAT_VEC2:
     36         case SH_INT_VEC2:
     37         case SH_BOOL_VEC2:
     38             return 5;
     39         case SH_FLOAT:
     40         case SH_INT:
     41         case SH_BOOL:
     42         case SH_SAMPLER_2D:
     43         case SH_SAMPLER_CUBE:
     44         case SH_SAMPLER_EXTERNAL_OES:
     45         case SH_SAMPLER_2D_RECT_ARB:
     46             return 6;
     47         default:
     48             ASSERT(false);
     49             return 7;
     50     }
     51 }
     52 }    // namespace
     53 
     54 int VariablePacker::GetNumComponentsPerRow(ShDataType type)
     55 {
     56     switch (type) {
     57         case SH_FLOAT_MAT4:
     58         case SH_FLOAT_MAT2:
     59         case SH_FLOAT_MAT2x4:
     60         case SH_FLOAT_MAT3x4:
     61         case SH_FLOAT_MAT4x2:
     62         case SH_FLOAT_MAT4x3:
     63         case SH_FLOAT_VEC4:
     64         case SH_INT_VEC4:
     65         case SH_BOOL_VEC4:
     66             return 4;
     67         case SH_FLOAT_MAT3:
     68         case SH_FLOAT_MAT2x3:
     69         case SH_FLOAT_MAT3x2:
     70         case SH_FLOAT_VEC3:
     71         case SH_INT_VEC3:
     72         case SH_BOOL_VEC3:
     73             return 3;
     74         case SH_FLOAT_VEC2:
     75         case SH_INT_VEC2:
     76         case SH_BOOL_VEC2:
     77             return 2;
     78         case SH_FLOAT:
     79         case SH_INT:
     80         case SH_BOOL:
     81         case SH_SAMPLER_2D:
     82         case SH_SAMPLER_CUBE:
     83         case SH_SAMPLER_EXTERNAL_OES:
     84         case SH_SAMPLER_2D_RECT_ARB:
     85             return 1;
     86         default:
     87             ASSERT(false);
     88             return 5;
     89     }
     90 }
     91 
     92 int VariablePacker::GetNumRows(ShDataType type)
     93 {
     94     switch (type) {
     95         case SH_FLOAT_MAT4:
     96         case SH_FLOAT_MAT2x4:
     97         case SH_FLOAT_MAT3x4:
     98         case SH_FLOAT_MAT4x3:
     99         case SH_FLOAT_MAT4x2:
    100             return 4;
    101         case SH_FLOAT_MAT3:
    102         case SH_FLOAT_MAT2x3:
    103         case SH_FLOAT_MAT3x2:
    104             return 3;
    105         case SH_FLOAT_MAT2:
    106             return 2;
    107         case SH_FLOAT_VEC4:
    108         case SH_INT_VEC4:
    109         case SH_BOOL_VEC4:
    110         case SH_FLOAT_VEC3:
    111         case SH_INT_VEC3:
    112         case SH_BOOL_VEC3:
    113         case SH_FLOAT_VEC2:
    114         case SH_INT_VEC2:
    115         case SH_BOOL_VEC2:
    116         case SH_FLOAT:
    117         case SH_INT:
    118         case SH_BOOL:
    119         case SH_SAMPLER_2D:
    120         case SH_SAMPLER_CUBE:
    121         case SH_SAMPLER_EXTERNAL_OES:
    122         case SH_SAMPLER_2D_RECT_ARB:
    123             return 1;
    124         default:
    125             ASSERT(false);
    126             return 100000;
    127     }
    128 }
    129 
    130 struct TVariableInfoComparer {
    131     bool operator()(const TVariableInfo& lhs, const TVariableInfo& rhs) const
    132     {
    133         int lhsSortOrder = GetSortOrder(lhs.type);
    134         int rhsSortOrder = GetSortOrder(rhs.type);
    135         if (lhsSortOrder != rhsSortOrder) {
    136             return lhsSortOrder < rhsSortOrder;
    137         }
    138         // Sort by largest first.
    139         return lhs.size > rhs.size;
    140     }
    141 };
    142 
    143 unsigned VariablePacker::makeColumnFlags(int column, int numComponentsPerRow)
    144 {
    145     return ((kColumnMask << (kNumColumns - numComponentsPerRow)) &
    146                     kColumnMask) >> column;
    147 }
    148 
    149 void VariablePacker::fillColumns(int topRow, int numRows, int column, int numComponentsPerRow)
    150 {
    151     unsigned columnFlags = makeColumnFlags(column, numComponentsPerRow);
    152     for (int r = 0; r < numRows; ++r) {
    153         int row = topRow + r;
    154         ASSERT((rows_[row] & columnFlags) == 0);
    155         rows_[row] |= columnFlags;
    156     }
    157 }
    158 
    159 bool VariablePacker::searchColumn(int column, int numRows, int* destRow, int* destSize)
    160 {
    161     ASSERT(destRow);
    162 
    163     for (; topNonFullRow_ < maxRows_ && rows_[topNonFullRow_] == kColumnMask;
    164          ++topNonFullRow_) {
    165     }
    166 
    167     for (; bottomNonFullRow_ >= 0 && rows_[bottomNonFullRow_] == kColumnMask;
    168          --bottomNonFullRow_) {
    169     }
    170 
    171     if (bottomNonFullRow_ - topNonFullRow_ + 1 < numRows) {
    172         return false;
    173     }
    174 
    175     unsigned columnFlags = makeColumnFlags(column, 1);
    176     int topGoodRow = 0;
    177     int smallestGoodTop = -1;
    178     int smallestGoodSize = maxRows_ + 1;
    179     int bottomRow = bottomNonFullRow_ + 1;
    180     bool found = false;
    181     for (int row = topNonFullRow_; row <= bottomRow; ++row) {
    182         bool rowEmpty = row < bottomRow ? ((rows_[row] & columnFlags) == 0) : false;
    183         if (rowEmpty) {
    184             if (!found) {
    185                 topGoodRow = row;
    186                 found = true;
    187             }
    188         } else {
    189             if (found) {
    190                 int size = row - topGoodRow;
    191                 if (size >= numRows && size < smallestGoodSize) {
    192                     smallestGoodSize = size;
    193                     smallestGoodTop = topGoodRow;
    194                 }
    195             }
    196             found = false;
    197         }
    198     }
    199     if (smallestGoodTop < 0) {
    200         return false;
    201     }
    202 
    203     *destRow = smallestGoodTop;
    204     if (destSize) {
    205         *destSize = smallestGoodSize;
    206     }
    207     return true;
    208 }
    209 
    210 bool VariablePacker::CheckVariablesWithinPackingLimits(int maxVectors, const TVariableInfoList& in_variables)
    211 {
    212     ASSERT(maxVectors > 0);
    213     maxRows_ = maxVectors;
    214     topNonFullRow_ = 0;
    215     bottomNonFullRow_ = maxRows_ - 1;
    216     TVariableInfoList variables(in_variables);
    217 
    218     // Check whether each variable fits in the available vectors.
    219     for (size_t i = 0; i < variables.size(); i++) {
    220         const TVariableInfo& variable = variables[i];
    221         if (variable.size > maxVectors / GetNumRows(variable.type)) {
    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         const TVariableInfo& variable = variables[ii];
    236         if (GetNumComponentsPerRow(variable.type) != 4) {
    237             break;
    238         }
    239         topNonFullRow_ += GetNumRows(variable.type) * variable.size;
    240     }
    241 
    242     if (topNonFullRow_ > maxRows_) {
    243         return false;
    244     }
    245 
    246     // Packs the 3 column variables.
    247     int num3ColumnRows = 0;
    248     for (; ii < variables.size(); ++ii) {
    249         const TVariableInfo& variable = variables[ii];
    250         if (GetNumComponentsPerRow(variable.type) != 3) {
    251             break;
    252         }
    253         num3ColumnRows += GetNumRows(variable.type) * variable.size;
    254     }
    255 
    256     if (topNonFullRow_ + num3ColumnRows > maxRows_) {
    257         return false;
    258     }
    259 
    260     fillColumns(topNonFullRow_, num3ColumnRows, 0, 3);
    261 
    262     // Packs the 2 column variables.
    263     int top2ColumnRow = topNonFullRow_ + num3ColumnRows;
    264     int twoColumnRowsAvailable = maxRows_ - top2ColumnRow;
    265     int rowsAvailableInColumns01 = twoColumnRowsAvailable;
    266     int rowsAvailableInColumns23 = twoColumnRowsAvailable;
    267     for (; ii < variables.size(); ++ii) {
    268         const TVariableInfo& variable = variables[ii];
    269         if (GetNumComponentsPerRow(variable.type) != 2) {
    270             break;
    271         }
    272         int numRows = GetNumRows(variable.type) * variable.size;
    273         if (numRows <= rowsAvailableInColumns01) {
    274             rowsAvailableInColumns01 -= numRows;
    275         } else if (numRows <= rowsAvailableInColumns23) {
    276             rowsAvailableInColumns23 -= numRows;
    277         } else {
    278             return false;
    279         }
    280     }
    281 
    282     int numRowsUsedInColumns01 =
    283         twoColumnRowsAvailable - rowsAvailableInColumns01;
    284     int numRowsUsedInColumns23 =
    285         twoColumnRowsAvailable - rowsAvailableInColumns23;
    286     fillColumns(top2ColumnRow, numRowsUsedInColumns01, 0, 2);
    287     fillColumns(maxRows_ - numRowsUsedInColumns23, numRowsUsedInColumns23,
    288                 2, 2);
    289 
    290     // Packs the 1 column variables.
    291     for (; ii < variables.size(); ++ii) {
    292         const TVariableInfo& variable = variables[ii];
    293         ASSERT(1 == GetNumComponentsPerRow(variable.type));
    294         int numRows = GetNumRows(variable.type) * variable.size;
    295         int smallestColumn = -1;
    296         int smallestSize = maxRows_ + 1;
    297         int topRow = -1;
    298         for (int column = 0; column < kNumColumns; ++column) {
    299             int row = 0;
    300             int size = 0;
    301             if (searchColumn(column, numRows, &row, &size)) {
    302                 if (size < smallestSize) {
    303                     smallestSize = size;
    304                     smallestColumn = column;
    305                     topRow = row;
    306                 }
    307             }
    308         }
    309 
    310         if (smallestColumn < 0) {
    311             return false;
    312         }
    313 
    314         fillColumns(topRow, numRows, smallestColumn, 1);
    315     }
    316 
    317     ASSERT(variables.size() == ii);
    318 
    319     return true;
    320 }
    321 
    322 
    323 
    324