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