kc3-lang/angle/src/compiler/translator/ImmutableString.cpp

• Show log

  Commit

• Hash : 89398b65
  Author :
  Date : 2018-03-21T17:30:50
  

  Avoid mangled name comparisons of 3-parameter functions
  
  The hash values used for looking up built-ins now encode whether the
  mangled name contains arrays, structs or interface blocks in its
  parameters list. This is written in the most significant bit of the
  hash value.
  
  We check this bit at the start of built-in lookup and if the bit is
  set we exit early. After that we know that the lookup name doesn't
  contain array, struct or interface block parameters.
  
  When we find a hash that matches a hash of a built-in function, we now
  know 3 things:
  1) the length of the mangled name matches
  2) the open parentheses in the mangled name matches
  3) the lookup doesn't contain array, struct or block parameters.
  
  Additionally, we have an if statement checking whether the function
  name matches. Collisions are only possible with functions that
  1) have the same name
  2) have the same number of parameters
  
  With these preconditions we can check beforehand whether collisions
  are possible for 3-parameter functions. If there are no collisions, we
  don't need to compare the full mangled name. This is similar to what
  was already being done with functions that had 0 to 2 parameters.
  
  This reduces shader_translator binary size by around 4 KB on Windows.
  
  Besides increased complexity, the tradeoff is that an exhaustive
  search of hash values for possible 3-parameter combinations is costly,
  so the gen_builtin_functions.py code generation script now takes
  around one minute to run on a high-end workstation. Due to this, the
  script now exits early if it detects it has already been run with the
  same inputs based on a hash value stored in
  builtin_symbols_hash_autogen.txt.
  
  BUG=angleproject:2267
  BUG=chromium:823856
  TEST=angle_unittests
  
  Change-Id: I3ff8c6eb85b90d3c4971ac8d73ee171a07a7e55f
  Reviewed-on: https://chromium-review.googlesource.com/973372
  Reviewed-by: Corentin Wallez <cwallez@chromium.org>
  Commit-Queue: Olli Etuaho <oetuaho@nvidia.com>
  

Download

• src/compiler/translator/ImmutableString.cpp

• //
  // Copyright (c) 2018 The ANGLE Project Authors. All rights reserved.
  // Use of this source code is governed by a BSD-style license that can be
  // found in the LICENSE file.
  //
  // ImmutableString.cpp: Wrapper for static or pool allocated char arrays, that are guaranteed to be
  // valid and unchanged for the duration of the compilation.
  //
  
  #include "compiler/translator/ImmutableString.h"
  
  std::ostream &operator<<(std::ostream &os, const sh::ImmutableString &str)
  {
      return os.write(str.data(), str.length());
  }
  
  #if defined(_MSC_VER)
  #pragma warning(disable : 4309)  // truncation of constant value
  #endif
  
  namespace sh
  {
  
  template <>
  const size_t ImmutableString::FowlerNollVoHash<4>::kFnvPrime = 16777619u;
  
  template <>
  const size_t ImmutableString::FowlerNollVoHash<4>::kFnvOffsetBasis = 0x811c9dc5u;
  
  template <>
  const size_t ImmutableString::FowlerNollVoHash<8>::kFnvPrime =
      static_cast<size_t>(1099511628211ull);
  
  template <>
  const size_t ImmutableString::FowlerNollVoHash<8>::kFnvOffsetBasis =
      static_cast<size_t>(0xcbf29ce484222325ull);
  
  uint32_t ImmutableString::mangledNameHash() const
  {
      const char *dataPtr              = data();
      uint32_t hash                    = static_cast<uint32_t>(FowlerNollVoHash<4>::kFnvOffsetBasis);
      const uint32_t kMaxSixBitValue   = (1u << 6) - 1u;
      uint32_t parenLocation           = kMaxSixBitValue;
      uint32_t hasArrayOrBlockParamBit = 0u;
      uint32_t index                   = 0;
      while (dataPtr[index] != '\0')
      {
          hash = hash ^ dataPtr[index];
          hash = hash * static_cast<uint32_t>(FowlerNollVoHash<4>::kFnvPrime);
          if (dataPtr[index] == '(')
          {
              // We should only reach here once, since this function should not be called with invalid
              // mangled names.
              ASSERT(parenLocation == kMaxSixBitValue);
              parenLocation = index;
          }
          else if (dataPtr[index] == '{' || dataPtr[index] == '[')
          {
              hasArrayOrBlockParamBit = 1u;
          }
          ++index;
      }
      // Should not be called with strings longer than 63 characters.
      ASSERT(index <= kMaxSixBitValue);
      return ((hash >> 13) ^ (hash & 0x1fff)) | (index << 19) | (parenLocation << 25) |
             (hasArrayOrBlockParamBit << 31);
  }
  
  }  // namespace sh
  

Download