<NME> strength_reduction_test.cpp
<BEF> // Copyright (c) 2017 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include <algorithm>
#include <cstdarg>
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_set>
#include <vector>

#include "gmock/gmock.h"
#include "test/opt/assembly_builder.h"
#include "test/opt/pass_fixture.h"
#include "test/opt/pass_utils.h"

namespace spvtools {
namespace opt {
namespace {

using ::testing::HasSubstr;
using ::testing::MatchesRegex;
using StrengthReductionBasicTest = PassTest<::testing::Test>;

// Test to make sure we replace 5*8.
TEST_F(StrengthReductionBasicTest, BasicReplaceMulBy8) {
  const std::vector<const char*> text = {
      // clang-format off
               "OpCapability Shader",
          "%1 = OpExtInstImport \"GLSL.std.450\"",
               "OpMemoryModel Logical GLSL450",
               "OpEntryPoint Vertex %main \"main\"",
               "OpName %main \"main\"",
       "%void = OpTypeVoid",
          "%4 = OpTypeFunction %void",
       "%uint = OpTypeInt 32 0",
     "%uint_5 = OpConstant %uint 5",
     "%uint_8 = OpConstant %uint 8",
       "%main = OpFunction %void None %4",
          "%8 = OpLabel",
          "%9 = OpIMul %uint %uint_5 %uint_8",
               "OpReturn",
               "OpFunctionEnd"
      // clang-format on
  };

  auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(
      JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);

  EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));
  const std::string& output = std::get<0>(result);
  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %uint %uint_5 %uint_3"));
}

// Test to make sure we replace 16*5.
TEST_F(StrengthReductionBasicTest, BasicReplaceMulBy16) {
  const std::vector<const char*> text = {
      // clang-format off
               "OpCapability Shader",
          "%1 = OpExtInstImport \"GLSL.std.450\"",
               "OpMemoryModel Logical GLSL450",
               "OpEntryPoint Vertex %main \"main\"",
               "OpName %main \"main\"",
       "%void = OpTypeVoid",
          "%4 = OpTypeFunction %void",
        "%int = OpTypeInt 32 1",
      "%int_16 = OpConstant %int 16",
      "%int_5 = OpConstant %int 5",
       "%main = OpFunction %void None %4",
          "%8 = OpLabel",
          "%9 = OpIMul %int %int_16 %int_5",
               "OpReturn",
               "OpFunctionEnd"
      // clang-format on
  };

  auto result = SinglePassRunAndDisassemble<opt::StrengthReductionPass>(
      JoinAllInsts(text), /* skip_nop = */ true);

  EXPECT_EQ(opt::Pass::Status::SuccessWithChange, std::get<1>(result));
  const std::string& output = std::get<0>(result);
  EXPECT_THAT(output, Not(HasSubstr("OpIMul")));
  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %int %int_5 %uint_4"));
}

// Test to make sure we replace a multiple of 32 and 4.
TEST_F(StrengthReductionBasicTest, BasicTwoPowersOf2) {
  // one of them for the bit shift.
  // clang-format off
  const std::string text = R"(
          OpCapability Shader
     %1 = OpExtInstImport "GLSL.std.450"
          OpMemoryModel Logical GLSL450
          OpEntryPoint Vertex %main "main"
          OpName %main "main"
  %void = OpTypeVoid
     %4 = OpTypeFunction %void
   %int = OpTypeInt 32 1
%int_32 = OpConstant %int 32
 %int_4 = OpConstant %int 4
  %main = OpFunction %void None %4
     %8 = OpLabel
     %9 = OpIMul %int %int_32 %int_4
          OpReturn
          OpFunctionEnd
)";
  // clang-format on
  auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(
      text, /* skip_nop = */ true, /* do_validation = */ false);

  EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));
  const std::string& output = std::get<0>(result);
  EXPECT_THAT(output, Not(HasSubstr("OpIMul")));
  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %int %int_4 %uint_5"));
}

// Test to make sure we don't replace 0*5.
TEST_F(StrengthReductionBasicTest, BasicDontReplace0) {
  const std::vector<const char*> text = {
      // clang-format off
               "OpCapability Shader",
          "%1 = OpExtInstImport \"GLSL.std.450\"",
               "OpMemoryModel Logical GLSL450",
               "OpEntryPoint Vertex %main \"main\"",
               "OpName %main \"main\"",
       "%void = OpTypeVoid",
          "%4 = OpTypeFunction %void",
        "%int = OpTypeInt 32 1",
      "%int_0 = OpConstant %int 0",
      "%int_5 = OpConstant %int 5",
       "%main = OpFunction %void None %4",
          "%8 = OpLabel",
          "%9 = OpIMul %int %int_0 %int_5",
               "OpReturn",
               "OpFunctionEnd"
      // clang-format on
  };

  auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(
      JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);

  EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
}

// Test to make sure we do not replace a multiple of 5 and 7.
TEST_F(StrengthReductionBasicTest, BasicNoChange) {
  const std::vector<const char*> text = {
      // clang-format off
             "OpCapability Shader",
        "%1 = OpExtInstImport \"GLSL.std.450\"",
             "OpMemoryModel Logical GLSL450",
             "OpEntryPoint Vertex %2 \"main\"",
             "OpName %2 \"main\"",
        "%3 = OpTypeVoid",
        "%4 = OpTypeFunction %3",
        "%5 = OpTypeInt 32 1",
        "%6 = OpTypeInt 32 0",
        "%7 = OpConstant %5 5",
        "%8 = OpConstant %5 7",
        "%2 = OpFunction %3 None %4",
        "%9 = OpLabel",
        "%10 = OpIMul %5 %7 %8",
             "OpReturn",
             "OpFunctionEnd",
      // clang-format on
  };

  auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(
      JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);

  EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));
}

// Test to make sure constants and types are reused and not duplicated.
TEST_F(StrengthReductionBasicTest, NoDuplicateConstantsAndTypes) {
  const std::vector<const char*> text = {
      // clang-format off
               "OpCapability Shader",
          "%1 = OpExtInstImport \"GLSL.std.450\"",
               "OpMemoryModel Logical GLSL450",
               "OpEntryPoint Vertex %main \"main\"",
               "OpName %main \"main\"",
       "%void = OpTypeVoid",
          "%4 = OpTypeFunction %void",
       "%uint = OpTypeInt 32 0",
     "%uint_8 = OpConstant %uint 8",
     "%uint_3 = OpConstant %uint 3",
       "%main = OpFunction %void None %4",
          "%8 = OpLabel",
          "%9 = OpIMul %uint %uint_8 %uint_3",
               "OpReturn",
               "OpFunctionEnd",
      // clang-format on
  };

  auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(
      JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);

  EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));
  const std::string& output = std::get<0>(result);
  EXPECT_THAT(output,
              Not(MatchesRegex(".*OpConstant %uint 3.*OpConstant %uint 3.*")));
  EXPECT_THAT(output, Not(MatchesRegex(".*OpTypeInt 32 0.*OpTypeInt 32 0.*")));
}

// Test to make sure we generate the constants only once
TEST_F(StrengthReductionBasicTest, BasicCreateOneConst) {
  const std::vector<const char*> text = {
      // clang-format off
               "OpCapability Shader",
          "%1 = OpExtInstImport \"GLSL.std.450\"",
               "OpMemoryModel Logical GLSL450",
               "OpEntryPoint Vertex %main \"main\"",
               "OpName %main \"main\"",
       "%void = OpTypeVoid",
          "%4 = OpTypeFunction %void",
       "%uint = OpTypeInt 32 0",
     "%uint_5 = OpConstant %uint 5",
     "%uint_9 = OpConstant %uint 9",
   "%uint_128 = OpConstant %uint 128",
       "%main = OpFunction %void None %4",
          "%8 = OpLabel",
          "%9 = OpIMul %uint %uint_5 %uint_128",
         "%10 = OpIMul %uint %uint_9 %uint_128",
               "OpReturn",
               "OpFunctionEnd"
      // clang-format on
  };

  auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(
      JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);

  EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));
  const std::string& output = std::get<0>(result);
  EXPECT_THAT(output, Not(HasSubstr("OpIMul")));
  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %uint %uint_5 %uint_7"));
  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %uint %uint_9 %uint_7"));
}

// Test to make sure we generate the instructions in the correct position and
// that the uses get replaced as well.  Here we check that the use in the return
// is replaced, we also check that we can replace two OpIMuls when one feeds the
// other.
TEST_F(StrengthReductionBasicTest, BasicCheckPositionAndReplacement) {
  // This is just the preamble to set up the test.
  const std::vector<const char*> common_text = {
      // clang-format off
               "OpCapability Shader",
          "%1 = OpExtInstImport \"GLSL.std.450\"",
               "OpMemoryModel Logical GLSL450",
               "OpEntryPoint Fragment %main \"main\" %gl_FragColor",
               "OpExecutionMode %main OriginUpperLeft",
               "OpName %main \"main\"",
               "OpName %foo_i1_ \"foo(i1;\"",
               "OpName %n \"n\"",
               "OpName %gl_FragColor \"gl_FragColor\"",
               "OpName %param \"param\"",
               "OpDecorate %gl_FragColor Location 0",
       "%void = OpTypeVoid",
          "%3 = OpTypeFunction %void",
        "%int = OpTypeInt 32 1",
"%_ptr_Function_int = OpTypePointer Function %int",
          "%8 = OpTypeFunction %int %_ptr_Function_int",
    "%int_256 = OpConstant %int 256",
      "%int_2 = OpConstant %int 2",
      "%float = OpTypeFloat 32",
    "%v4float = OpTypeVector %float 4",
"%_ptr_Output_v4float = OpTypePointer Output %v4float",
"%gl_FragColor = OpVariable %_ptr_Output_v4float Output",
    "%float_1 = OpConstant %float 1",
     "%int_10 = OpConstant %int 10",
  "%float_0_375 = OpConstant %float 0.375",
  "%float_0_75 = OpConstant %float 0.75",
       "%uint = OpTypeInt 32 0",
     "%uint_8 = OpConstant %uint 8",
     "%uint_1 = OpConstant %uint 1",
       "%main = OpFunction %void None %3",
          "%5 = OpLabel",
      "%param = OpVariable %_ptr_Function_int Function",
               "OpStore %param %int_10",
         "%26 = OpFunctionCall %int %foo_i1_ %param",
         "%27 = OpConvertSToF %float %26",
         "%28 = OpFDiv %float %float_1 %27",
         "%31 = OpCompositeConstruct %v4float %28 %float_0_375 %float_0_75 %float_1",
               "OpStore %gl_FragColor %31",
               "OpReturn",
               "OpFunctionEnd"
      // clang-format on
  };

  // This is the real test.  The two OpIMul should be replaced.  The expected
  // output is in |foo_after|.
  const std::vector<const char*> foo_before = {
      // clang-format off
    "%foo_i1_ = OpFunction %int None %8",
          "%n = OpFunctionParameter %_ptr_Function_int",
         "%11 = OpLabel",
         "%12 = OpLoad %int %n",
         "%14 = OpIMul %int %12 %int_256",
         "%16 = OpIMul %int %14 %int_2",
               "OpReturnValue %16",
               "OpFunctionEnd",

      // clang-format on
  };

  const std::vector<const char*> foo_after = {
      // clang-format off
    "%foo_i1_ = OpFunction %int None %8",
          "%n = OpFunctionParameter %_ptr_Function_int",
         "%11 = OpLabel",
         "%12 = OpLoad %int %n",
         "%33 = OpShiftLeftLogical %int %12 %uint_8",
         "%34 = OpShiftLeftLogical %int %33 %uint_1",
               "OpReturnValue %34",
               "OpFunctionEnd",
      // clang-format on
  };

  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
  SinglePassRunAndCheck<StrengthReductionPass>(
      JoinAllInsts(Concat(common_text, foo_before)),
      JoinAllInsts(Concat(common_text, foo_after)),
      /* skip_nop = */ true, /* do_validate = */ true);
}

// Test that, when the result of an OpIMul instruction has more than 1 use, and
// the instruction is replaced, all of the uses of the results are replace with
// the new result.
TEST_F(StrengthReductionBasicTest, BasicTestMultipleReplacements) {
  // This is just the preamble to set up the test.
  const std::vector<const char*> common_text = {
      // clang-format off
               "OpCapability Shader",
          "%1 = OpExtInstImport \"GLSL.std.450\"",
               "OpMemoryModel Logical GLSL450",
               "OpEntryPoint Fragment %main \"main\" %gl_FragColor",
               "OpExecutionMode %main OriginUpperLeft",
               "OpName %main \"main\"",
               "OpName %foo_i1_ \"foo(i1;\"",
               "OpName %n \"n\"",
               "OpName %gl_FragColor \"gl_FragColor\"",
               "OpName %param \"param\"",
               "OpDecorate %gl_FragColor Location 0",
       "%void = OpTypeVoid",
          "%3 = OpTypeFunction %void",
        "%int = OpTypeInt 32 1",
"%_ptr_Function_int = OpTypePointer Function %int",
          "%8 = OpTypeFunction %int %_ptr_Function_int",
    "%int_256 = OpConstant %int 256",
      "%int_2 = OpConstant %int 2",
      "%float = OpTypeFloat 32",
    "%v4float = OpTypeVector %float 4",
"%_ptr_Output_v4float = OpTypePointer Output %v4float",
"%gl_FragColor = OpVariable %_ptr_Output_v4float Output",
    "%float_1 = OpConstant %float 1",
     "%int_10 = OpConstant %int 10",
  "%float_0_375 = OpConstant %float 0.375",
  "%float_0_75 = OpConstant %float 0.75",
       "%uint = OpTypeInt 32 0",
     "%uint_8 = OpConstant %uint 8",
     "%uint_1 = OpConstant %uint 1",
       "%main = OpFunction %void None %3",
          "%5 = OpLabel",
      "%param = OpVariable %_ptr_Function_int Function",
               "OpStore %param %int_10",
         "%26 = OpFunctionCall %int %foo_i1_ %param",
         "%27 = OpConvertSToF %float %26",
         "%28 = OpFDiv %float %float_1 %27",
         "%31 = OpCompositeConstruct %v4float %28 %float_0_375 %float_0_75 %float_1",
               "OpStore %gl_FragColor %31",
               "OpReturn",
               "OpFunctionEnd"
      // clang-format on
  };

  // This is the real test.  The two OpIMul instructions should be replaced.  In
  // particular, we want to be sure that both uses of %16 are changed to use the
  // new result.
  const std::vector<const char*> foo_before = {
      // clang-format off
    "%foo_i1_ = OpFunction %int None %8",
          "%n = OpFunctionParameter %_ptr_Function_int",
         "%11 = OpLabel",
         "%12 = OpLoad %int %n",
         "%14 = OpIMul %int %12 %int_256",
         "%16 = OpIMul %int %14 %int_2",
         "%17 = OpIAdd %int %14 %16",
               "OpReturnValue %17",
               "OpFunctionEnd",

      // clang-format on
  };

  const std::vector<const char*> foo_after = {
      // clang-format off
    "%foo_i1_ = OpFunction %int None %8",
          "%n = OpFunctionParameter %_ptr_Function_int",
         "%11 = OpLabel",
         "%12 = OpLoad %int %n",
         "%34 = OpShiftLeftLogical %int %12 %uint_8",
         "%35 = OpShiftLeftLogical %int %34 %uint_1",
         "%17 = OpIAdd %int %34 %35",
               "OpReturnValue %17",
               "OpFunctionEnd",
      // clang-format on
  };

  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);
  SinglePassRunAndCheck<StrengthReductionPass>(
      JoinAllInsts(Concat(common_text, foo_before)),
      JoinAllInsts(Concat(common_text, foo_after)),
      /* skip_nop = */ true, /* do_validate = */ true);
}

}  // namespace
}  // namespace opt
}  // namespace spvtools

<MSG> Tests: Add optional dependency on Effcee stateful matcher

Add Effcee as an optional dependency for use in tests.  In future it will
be a required dependency.

Effcee is a stateful pattern matcher that has much of the functionality
of LLVM's FileCheck, except in library form.  Effcee makes it much easier
to write tests for optimization passes.

Demonstrate its use in a test for the strength-reduction pass.

Update README.md with example commands of how to get sources.

Update Appveyor and Travis-CI build rules.

Also: Include test libraries if not SPIRV_SKIP_TESTS
- SPIRV_SKIP_TESTS is implied by SPIRV_SKIP_EXECUTABLES

<DFF> @@ -63,36 +63,45 @@ TEST_F(StrengthReductionBasicTest, BasicReplaceMulBy8) {
   EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %uint %uint_5 %uint_3"));
 }
 
-// Test to make sure we replace 16*5.
+// TODO(dneto): Add Effcee as required dependency, and make this unconditional.
+#ifdef SPIRV_EFFCEE
+// Test to make sure we replace 16*5
+// Also demonstrate use of Effcee matching.
 TEST_F(StrengthReductionBasicTest, BasicReplaceMulBy16) {
-  const std::vector<const char*> text = {
-      // clang-format off
-               "OpCapability Shader",
-          "%1 = OpExtInstImport \"GLSL.std.450\"",
-               "OpMemoryModel Logical GLSL450",
-               "OpEntryPoint Vertex %main \"main\"",
-               "OpName %main \"main\"",
-       "%void = OpTypeVoid",
-          "%4 = OpTypeFunction %void",
-        "%int = OpTypeInt 32 1",
-      "%int_16 = OpConstant %int 16",
-      "%int_5 = OpConstant %int 5",
-       "%main = OpFunction %void None %4",
-          "%8 = OpLabel",
-          "%9 = OpIMul %int %int_16 %int_5",
-               "OpReturn",
-               "OpFunctionEnd"
-      // clang-format on
-  };
-
-  auto result = SinglePassRunAndDisassemble<opt::StrengthReductionPass>(
-      JoinAllInsts(text), /* skip_nop = */ true);
-
-  EXPECT_EQ(opt::Pass::Status::SuccessWithChange, std::get<1>(result));
-  const std::string& output = std::get<0>(result);
-  EXPECT_THAT(output, Not(HasSubstr("OpIMul")));
-  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %int %int_5 %uint_4"));
+  const std::string text = R"(
+               OpCapability Shader
+          %1 = OpExtInstImport "GLSL.std.450"
+               OpMemoryModel Logical GLSL450
+               OpEntryPoint Vertex %main "main"
+               OpName %main "main"
+       %void = OpTypeVoid
+          %4 = OpTypeFunction %void
+; We know disassembly will produce %uint here, but
+;  CHECK: %uint = OpTypeInt 32 0
+;  CHECK-DAG: [[five:%[a-zA-Z_\d]+]] = OpConstant %uint 5
+
+; We have RE2 regular expressions, so \w matches [_a-zA-Z0-9].
+; This shows the preferred pattern for matching SPIR-V identifiers.
+; (We could have cheated in this case since we know the disassembler will
+; generate the 'nice' name of "%uint_4".
+;  CHECK-DAG: [[four:%\w+]] = OpConstant %uint 4
+       %uint = OpTypeInt 32 0
+     %uint_5 = OpConstant %uint 5
+    %uint_16 = OpConstant %uint 16
+       %main = OpFunction %void None %4
+; CHECK: OpLabel
+          %8 = OpLabel
+; CHECK-NEXT: OpShiftLeftLogical %uint [[five]] [[four]]
+; The multiplication disappears.
+; CHECK-NOT: OpIMul
+          %9 = OpIMul %uint %uint_16 %uint_5
+               OpReturn
+; CHECK: OpFunctionEnd
+               OpFunctionEnd)";
+
+  SinglePassRunAndMatch<opt::StrengthReductionPass>(text);
 }
+#endif
 
 // Test to make sure we replace a multiple of 32 and 4.
 TEST_F(StrengthReductionBasicTest, BasicTwoPowersOf2) {

{'commit': 'diff --git a/.appveyor.yml b/.appveyor.yml\nindex 309fd125..50fe13f1 100644\n--- a/.appveyor.yml\n+++ b/.appveyor.yml\n@@ -29,6 +29,8 @@ matrix:\n install:\n   - git clone https://github.com/KhronosGroup/SPIRV-Headers.git external/spirv-headers\n   - git clone https://github.com/google/googletest.git external/googletest\n+  - git clone https://github.com/google/effcee.git external/effcee\n+  - git clone https://github.com/google/re2.git external/re2\n \n build:\n   parallel: true  # enable MSBuild parallel builds\ndiff --git a/.travis.yml b/.travis.yml\nindex ed1f4e87..ba3d2524 100644\n--- a/.travis.yml\n+++ b/.travis.yml\n@@ -56,6 +56,8 @@ before_install:\n before_script:\n   - git clone --depth=1 https://github.com/KhronosGroup/SPIRV-Headers external/spirv-headers\n   - git clone --depth=1 https://github.com/google/googletest          external/googletest\n+  - git clone --depth=1 https://github.com/google/effcee              external/effcee\n+  - git clone --depth=1 https://github.com/google/re2                 external/re2\n \n script:\n   # Due to the limitation of Travis platform, we cannot start too many concurrent jobs.\ndiff --git a/CHANGES b/CHANGES\nindex dd2c5bef..690a4401 100644\n--- a/CHANGES\n+++ b/CHANGES\n@@ -3,6 +3,9 @@ Revision history for SPIRV-Tools\n v2017.1-dev 2017-09-01\n  - Update README with details on the public_spirv_tools_dev@khronos.org mailing list.\n  - General:\n+   - Add the \'effcee\' library as an optional dependency for use in tests.\n+     Eventually it will be a required dependency, once downstream projects have\n+     a chance to adjust.\n    - Avoid static-duration variables of class type (with constructors).\n  - Validator:\n    - Type check basic arithmetic operations\ndiff --git a/CMakeLists.txt b/CMakeLists.txt\nindex 4ce96153..48eb5a03 100644\n--- a/CMakeLists.txt\n+++ b/CMakeLists.txt\n@@ -182,6 +182,10 @@ endif()\n \n add_subdirectory(external)\n \n+if (TARGET effcee)\n+  add_definitions(-DSPIRV_EFFCEE)\n+endif()\n+\n add_subdirectory(source)\n add_subdirectory(tools)\n \ndiff --git a/README.md b/README.md\nindex 2e61851d..1daefb58 100644\n--- a/README.md\n+++ b/README.md\n@@ -171,6 +171,11 @@ We intend to maintain a linear history on the GitHub `master` branch.\n * `example`: demo code of using SPIRV-Tools APIs\n * `external/googletest`: Intended location for the\n   [googletest][googletest] sources, not provided\n+* `external/effcee`: Location of [Effcee][effcee] sources, if the `effcee` library\n+  is not already configured by an enclosing project.\n+* `external/re2`: Location of [RE2][re2] sources, if the `effcee` library is not already\n+  configured by an enclosing project.\n+  (The Effcee project already requires RE2.)\n * `include/`: API clients should add this directory to the include search path\n * `external/spirv-headers`: Intended location for\n   [SPIR-V headers][spirv-headers], not provided\n@@ -179,6 +184,14 @@ We intend to maintain a linear history on the GitHub `master` branch.\n * `test/`: Tests, using the [googletest][googletest] framework\n * `tools/`: Command line executables\n \n+Example of getting sources, assuming SPIRV-Tools is configured as a standalone project:\n+\n+    git clone https://github.com/KhronosGroup/SPIRV-Tools.git   spirv-tools\n+    git clone https://github.com/KhronosGroup/SPIRV-Headers.git spirv-tools/external/spirv-headers\n+    git clone https://github.com/google/googletest.git          spirv-tools/external/googletest\n+    git clone https://github.com/google/effcee.git              spirv-tools/external/effcee\n+    git clone https://github.com/google/re2.git                 spirv-tools/external/re2\n+\n ### Tests\n \n The project contains a number of tests, used to drive development\n@@ -197,6 +210,18 @@ tests:\n The fix is included on the googletest master branch any time after 2015-11-10.\n In particular, googletest must be newer than version 1.7.0.\n \n+### Optional dependency on Effcee\n+\n+Some tests depend on the [Effcee][effcee] library for stateful matching.\n+Effcee itself depends on [RE2][re2].\n+\n+* If SPIRV-Tools is configured as part of a larger project that already uses\n+  Effcee, then that project should include Effcee before SPIRV-Tools.\n+* Otherwise, SPIRV-Tools expects Effcee sources to appear in `external/effcee`\n+  and RE2 sources to appear in `external/re2`.\n+\n+Currently Effcee is an optional dependency, but soon it will be required.\n+\n ## Build\n \n The project uses [CMake][cmake] to generate platform-specific build\n@@ -470,6 +495,8 @@ limitations under the License.\n [googletest]: https://github.com/google/googletest\n [googletest-pull-612]: https://github.com/google/googletest/pull/612\n [googletest-issue-610]: https://github.com/google/googletest/issues/610\n+[effcee]: https://github.com/google/effcee\n+[re2]: https://github.com/google/re2\n [CMake]: https://cmake.org/\n [cpp-style-guide]: https://google.github.io/styleguide/cppguide.html\n [clang-sanitizers]: http://clang.llvm.org/docs/UsersManual.html#controlling-code-generation\ndiff --git a/external/CMakeLists.txt b/external/CMakeLists.txt\nindex e710ddda..412d8c3b 100644\n--- a/external/CMakeLists.txt\n+++ b/external/CMakeLists.txt\n@@ -27,7 +27,7 @@ else()\n     "SPIRV-Headers was not found - please checkout a copy under external/.")\n endif()\n \n-if (NOT ${SPIRV_SKIP_EXECUTABLES})\n+if (NOT ${SPIRV_SKIP_TESTS})\n   # Find gmock if we can. If it\'s not already configured, then try finding\n   # it in external/googletest.\n   if (TARGET gmock)\n@@ -54,4 +54,48 @@ if (NOT ${SPIRV_SKIP_EXECUTABLES})\n       set_property(TARGET ${target} PROPERTY FOLDER GoogleTest)\n     endforeach()\n   endif()\n+\n+  # Find Effcee and RE2, for testing.\n+  # Optional for now, but eventually we\'ll make this required.\n+\n+  # First find RE2, since Effcee depends on it.\n+  # If already configured, then use that.  Otherwise, prefer to find it under \'re2\'\n+  # in this directory.\n+  if (NOT TARGET re2)\n+    # If we are configuring RE2, then turn off its testing.  It takes a long time and\n+    # does not add much value for us.  If an enclosing project configured RE2, then it\n+    # has already chosen whether to enable RE2 tesitng.\n+    set(RE2_BUILD_TESTING OFF CACHE STRING "Run RE2 Tests")\n+    if (NOT RE2_SOURCE_DIR)\n+      if (EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/re2)\n+        set(RE2_SOURCE_DIR "${CMAKE_CURRENT_SOURCE_DIR}/re2" CACHE STRING "RE2 source dir" )\n+      endif()\n+    endif()\n+  endif()\n+\n+  if (NOT TARGET effcee)\n+    # Expect to find effcee in this directory.\n+    if (EXISTS ${CMAKE_CURRENT_SOURCE_DIR}/effcee)\n+      # If we\'re configuring RE2 (via Effcee), then turn off RE2 testing.\n+      if (NOT TARGET re2)\n+        set(RE2_BUILD_TESTING OFF)\n+      endif()\n+      if (MSVC)\n+        # SPIRV-Tools uses the shared CRT with MSVC.  Tell Effcee to do the same.\n+        set(EFFCEE_ENABLE_SHARED_CRT ON)\n+      endif()\n+      add_subdirectory(effcee)\n+      set_property(TARGET effcee PROPERTY FOLDER Effcee)\n+      # Turn off warnings for effcee and re2\n+      set_property(TARGET effcee APPEND PROPERTY COMPILE_OPTIONS -w)\n+      set_property(TARGET re2 APPEND PROPERTY COMPILE_OPTIONS -w)\n+    endif()\n+  endif()\n+  # TODO(dneto): Eventually, require this.\n+  if (TARGET effcee)\n+    message(STATUS "SPIRV-Tools: Effcee is configured")\n+  else()\n+    message(STATUS "SPIRV-Tools: Effcee is not configured.  Skipping Effcee-based tests.")\n+  endif()\n+\n endif()\ndiff --git a/test/CMakeLists.txt b/test/CMakeLists.txt\nindex 1b8cad29..176aa91e 100644\n--- a/test/CMakeLists.txt\n+++ b/test/CMakeLists.txt\n@@ -39,6 +39,8 @@ function(add_spvtools_unittest)\n     spvtools_default_compile_options(${target})\n     if(${COMPILER_IS_LIKE_GNU})\n       target_compile_options(${target} PRIVATE -Wno-undef)\n+      # Effcee and RE2 headers exhibit shadowing.\n+      target_compile_options(${target} PRIVATE -Wno-shadow)\n     endif()\n     if("${CMAKE_CXX_COMPILER_ID}" STREQUAL "MSVC")\n       # Disable C4503 "decorated name length exceeded" warning,\n@@ -56,7 +58,14 @@ function(add_spvtools_unittest)\n       ${gtest_SOURCE_DIR}/include\n       ${gmock_SOURCE_DIR}/include\n     )\n+    if (TARGET effcee)\n+      # If using Effcee for testing, then add its include directory.\n+      target_include_directories(${target} PRIVATE ${effcee_SOURCE_DIR})\n+    endif()\n     target_link_libraries(${target} PRIVATE ${ARG_LIBS})\n+    if (TARGET effcee)\n+      target_link_libraries(${target} PRIVATE effcee)\n+    endif()\n     target_link_libraries(${target} PRIVATE gmock_main)\n     add_test(NAME spirv-tools-${target} COMMAND ${target})\n     set_property(TARGET ${target} PROPERTY FOLDER "SPIRV-Tools tests")\ndiff --git a/test/opt/pass_fixture.h b/test/opt/pass_fixture.h\nindex 93ef916a..7ad71817 100644\n--- a/test/opt/pass_fixture.h\n+++ b/test/opt/pass_fixture.h\n@@ -22,6 +22,10 @@\n \n #include <gtest/gtest.h>\n \n+#ifdef SPIRV_EFFCEE\n+#include "effcee/effcee.h"\n+#endif\n+\n #include "opt/build_module.h"\n #include "opt/make_unique.h"\n #include "opt/pass_manager.h"\n@@ -149,6 +153,25 @@ class PassTest : public TestT {\n       std::forward<Args>(args)...);\n   }\n \n+#ifdef SPIRV_EFFCEE\n+  // Runs a single pass of class |PassT| on the binary assembled from the\n+  // |original| assembly, then runs an Effcee matcher over the disassembled\n+  // result, using checks parsed from |original|.  Always skips OpNop.\n+  // This does *not* involve pass manager.  Callers are suggested to use\n+  // SCOPED_TRACE() for better messages.\n+  template <typename PassT, typename... Args>\n+  void SinglePassRunAndMatch(const std::string& original, Args&&... args) {\n+    const bool skip_nop = true;\n+    auto pass_result = SinglePassRunAndDisassemble<PassT>(\n+        original, skip_nop, std::forward<Args>(args)...);\n+    auto disassembly = std::get<0>(pass_result);\n+    auto match_result = effcee::Match(disassembly, original);\n+    EXPECT_EQ(effcee::Result::Status::Ok, match_result.status())\n+        << match_result.message() << "\\nChecking result:\\n"\n+        << disassembly;\n+  }\n+#endif\n+\n   // Adds a pass to be run.\n   template <typename PassT, typename... Args>\n   void AddPass(Args&&... args) {\ndiff --git a/test/opt/strength_reduction_test.cpp b/test/opt/strength_reduction_test.cpp\nindex 541be603..32eb4c3c 100644\n--- a/test/opt/strength_reduction_test.cpp\n+++ b/test/opt/strength_reduction_test.cpp\n@@ -63,36 +63,45 @@ TEST_F(StrengthReductionBasicTest, BasicReplaceMulBy8) {\n   EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %uint %uint_5 %uint_3"));\n }\n \n-// Test to make sure we replace 16*5.\n+// TODO(dneto): Add Effcee as required dependency, and make this unconditional.\n+#ifdef SPIRV_EFFCEE\n+// Test to make sure we replace 16*5\n+// Also demonstrate use of Effcee matching.\n TEST_F(StrengthReductionBasicTest, BasicReplaceMulBy16) {\n-  const std::vector<const char*> text = {\n-      // clang-format off\n-               "OpCapability Shader",\n-          "%1 = OpExtInstImport \\"GLSL.std.450\\"",\n-               "OpMemoryModel Logical GLSL450",\n-               "OpEntryPoint Vertex %main \\"main\\"",\n-               "OpName %main \\"main\\"",\n-       "%void = OpTypeVoid",\n-          "%4 = OpTypeFunction %void",\n-        "%int = OpTypeInt 32 1",\n-      "%int_16 = OpConstant %int 16",\n-      "%int_5 = OpConstant %int 5",\n-       "%main = OpFunction %void None %4",\n-          "%8 = OpLabel",\n-          "%9 = OpIMul %int %int_16 %int_5",\n-               "OpReturn",\n-               "OpFunctionEnd"\n-      // clang-format on\n-  };\n-\n-  auto result = SinglePassRunAndDisassemble<opt::StrengthReductionPass>(\n-      JoinAllInsts(text), /* skip_nop = */ true);\n-\n-  EXPECT_EQ(opt::Pass::Status::SuccessWithChange, std::get<1>(result));\n-  const std::string& output = std::get<0>(result);\n-  EXPECT_THAT(output, Not(HasSubstr("OpIMul")));\n-  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %int %int_5 %uint_4"));\n+  const std::string text = R"(\n+               OpCapability Shader\n+          %1 = OpExtInstImport "GLSL.std.450"\n+               OpMemoryModel Logical GLSL450\n+               OpEntryPoint Vertex %main "main"\n+               OpName %main "main"\n+       %void = OpTypeVoid\n+          %4 = OpTypeFunction %void\n+; We know disassembly will produce %uint here, but\n+;  CHECK: %uint = OpTypeInt 32 0\n+;  CHECK-DAG: [[five:%[a-zA-Z_\\d]+]] = OpConstant %uint 5\n+\n+; We have RE2 regular expressions, so \\w matches [_a-zA-Z0-9].\n+; This shows the preferred pattern for matching SPIR-V identifiers.\n+; (We could have cheated in this case since we know the disassembler will\n+; generate the \'nice\' name of "%uint_4".\n+;  CHECK-DAG: [[four:%\\w+]] = OpConstant %uint 4\n+       %uint = OpTypeInt 32 0\n+     %uint_5 = OpConstant %uint 5\n+    %uint_16 = OpConstant %uint 16\n+       %main = OpFunction %void None %4\n+; CHECK: OpLabel\n+          %8 = OpLabel\n+; CHECK-NEXT: OpShiftLeftLogical %uint [[five]] [[four]]\n+; The multiplication disappears.\n+; CHECK-NOT: OpIMul\n+          %9 = OpIMul %uint %uint_16 %uint_5\n+               OpReturn\n+; CHECK: OpFunctionEnd\n+               OpFunctionEnd)";\n+\n+  SinglePassRunAndMatch<opt::StrengthReductionPass>(text);\n }\n+#endif\n \n // Test to make sure we replace a multiple of 32 and 4.\n TEST_F(StrengthReductionBasicTest, BasicTwoPowersOf2) {\n', 'commit_subject': 'Tests: Add optional dependency on Effcee stateful matcher', 'repo_name': 'KhronosGroup/SPIRV-Tools', 'committer': {'name': 'David Neto', 'email': '3f97edd74090acb1bf9368021b16e328eddf820c@google.com', 'time_sec': '1510590861', 'tz_offset': '-300', 'date': {'seconds': '1510590861'}}, 'commit_tree': '68576ebf22954815cdbe28e7d34a8cae68f9f7b0', 'commit_message': "Tests: Add optional dependency on Effcee stateful matcher\n\nAdd Effcee as an optional dependency for use in tests.  In future it will\nbe a required dependency.\n\nEffcee is a stateful pattern matcher that has much of the functionality\nof LLVM's FileCheck, except in library form.  Effcee makes it much easier\nto write tests for optimization passes.\n\nDemonstrate its use in a test for the strength-reduction pass.\n\nUpdate README.md with example commands of how to get sources.\n\nUpdate Appveyor and Travis-CI build rules.\n\nAlso: Include test libraries if not SPIRV_SKIP_TESTS\n- SPIRV_SKIP_TESTS is implied by SPIRV_SKIP_EXECUTABLES\n", 'language_name': 'C', 'license': 'apache-2.0', 'hunks': '@@ -63,36 +63,45 @@ TEST_F(StrengthReductionBasicTest, BasicReplaceMulBy8) {\n   EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %uint %uint_5 %uint_3"));\n }\n \n-// Test to make sure we replace 16*5.\n+// TODO(dneto): Add Effcee as required dependency, and make this unconditional.\n+#ifdef SPIRV_EFFCEE\n+// Test to make sure we replace 16*5\n+// Also demonstrate use of Effcee matching.\n TEST_F(StrengthReductionBasicTest, BasicReplaceMulBy16) {\n-  const std::vector<const char*> text = {\n-      // clang-format off\n-               "OpCapability Shader",\n-          "%1 = OpExtInstImport \\"GLSL.std.450\\"",\n-               "OpMemoryModel Logical GLSL450",\n-               "OpEntryPoint Vertex %main \\"main\\"",\n-               "OpName %main \\"main\\"",\n-       "%void = OpTypeVoid",\n-          "%4 = OpTypeFunction %void",\n-        "%int = OpTypeInt 32 1",\n-      "%int_16 = OpConstant %int 16",\n-      "%int_5 = OpConstant %int 5",\n-       "%main = OpFunction %void None %4",\n-          "%8 = OpLabel",\n-          "%9 = OpIMul %int %int_16 %int_5",\n-               "OpReturn",\n-               "OpFunctionEnd"\n-      // clang-format on\n-  };\n-\n-  auto result = SinglePassRunAndDisassemble<opt::StrengthReductionPass>(\n-      JoinAllInsts(text), /* skip_nop = */ true);\n-\n-  EXPECT_EQ(opt::Pass::Status::SuccessWithChange, std::get<1>(result));\n-  const std::string& output = std::get<0>(result);\n-  EXPECT_THAT(output, Not(HasSubstr("OpIMul")));\n-  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %int %int_5 %uint_4"));\n+  const std::string text = R"(\n+               OpCapability Shader\n+          %1 = OpExtInstImport "GLSL.std.450"\n+               OpMemoryModel Logical GLSL450\n+               OpEntryPoint Vertex %main "main"\n+               OpName %main "main"\n+       %void = OpTypeVoid\n+          %4 = OpTypeFunction %void\n+; We know disassembly will produce %uint here, but\n+;  CHECK: %uint = OpTypeInt 32 0\n+;  CHECK-DAG: [[five:%[a-zA-Z_\\d]+]] = OpConstant %uint 5\n+\n+; We have RE2 regular expressions, so \\w matches [_a-zA-Z0-9].\n+; This shows the preferred pattern for matching SPIR-V identifiers.\n+; (We could have cheated in this case since we know the disassembler will\n+; generate the \'nice\' name of "%uint_4".\n+;  CHECK-DAG: [[four:%\\w+]] = OpConstant %uint 4\n+       %uint = OpTypeInt 32 0\n+     %uint_5 = OpConstant %uint 5\n+    %uint_16 = OpConstant %uint 16\n+       %main = OpFunction %void None %4\n+; CHECK: OpLabel\n+          %8 = OpLabel\n+; CHECK-NEXT: OpShiftLeftLogical %uint [[five]] [[four]]\n+; The multiplication disappears.\n+; CHECK-NOT: OpIMul\n+          %9 = OpIMul %uint %uint_16 %uint_5\n+               OpReturn\n+; CHECK: OpFunctionEnd\n+               OpFunctionEnd)";\n+\n+  SinglePassRunAndMatch<opt::StrengthReductionPass>(text);\n }\n+#endif\n \n // Test to make sure we replace a multiple of 32 and 4.\n TEST_F(StrengthReductionBasicTest, BasicTwoPowersOf2) {\n', 'addition_count': 37, 'deletion_count': 28, 'src_file': 'a/test/opt/strength_reduction_test.cpp', 'tgt_file': 'b/test/opt/strength_reduction_test.cpp', 'file_extension': '.cpp', 'before_file': '// Copyright (c) 2017 Google Inc.\n//\n// Licensed under the Apache License, Version 2.0 (the "License");\n// you may not use this file except in compliance with the License.\n// You may obtain a copy of the License at\n//\n//     http://www.apache.org/licenses/LICENSE-2.0\n//\n// Unless required by applicable law or agreed to in writing, software\n// distributed under the License is distributed on an "AS IS" BASIS,\n// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n// See the License for the specific language governing permissions and\n// limitations under the License.\n\n#include <algorithm>\n#include <cstdarg>\n#include <iostream>\n#include <sstream>\n#include <string>\n#include <unordered_set>\n#include <vector>\n\n#include "gmock/gmock.h"\n#include "test/opt/assembly_builder.h"\n#include "test/opt/pass_fixture.h"\n#include "test/opt/pass_utils.h"\n\nnamespace spvtools {\nnamespace opt {\nnamespace {\n\nusing ::testing::HasSubstr;\nusing ::testing::MatchesRegex;\nusing StrengthReductionBasicTest = PassTest<::testing::Test>;\n\n// Test to make sure we replace 5*8.\nTEST_F(StrengthReductionBasicTest, BasicReplaceMulBy8) {\n  const std::vector<const char*> text = {\n      // clang-format off\n               "OpCapability Shader",\n          "%1 = OpExtInstImport \\"GLSL.std.450\\"",\n               "OpMemoryModel Logical GLSL450",\n               "OpEntryPoint Vertex %main \\"main\\"",\n               "OpName %main \\"main\\"",\n       "%void = OpTypeVoid",\n          "%4 = OpTypeFunction %void",\n       "%uint = OpTypeInt 32 0",\n     "%uint_5 = OpConstant %uint 5",\n     "%uint_8 = OpConstant %uint 8",\n       "%main = OpFunction %void None %4",\n          "%8 = OpLabel",\n          "%9 = OpIMul %uint %uint_5 %uint_8",\n               "OpReturn",\n               "OpFunctionEnd"\n      // clang-format on\n  };\n\n  auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(\n      JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);\n\n  EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));\n  const std::string& output = std::get<0>(result);\n  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %uint %uint_5 %uint_3"));\n}\n\n// Test to make sure we replace 16*5.\nTEST_F(StrengthReductionBasicTest, BasicReplaceMulBy16) {\n  const std::vector<const char*> text = {\n      // clang-format off\n               "OpCapability Shader",\n          "%1 = OpExtInstImport \\"GLSL.std.450\\"",\n               "OpMemoryModel Logical GLSL450",\n               "OpEntryPoint Vertex %main \\"main\\"",\n               "OpName %main \\"main\\"",\n       "%void = OpTypeVoid",\n          "%4 = OpTypeFunction %void",\n        "%int = OpTypeInt 32 1",\n      "%int_16 = OpConstant %int 16",\n      "%int_5 = OpConstant %int 5",\n       "%main = OpFunction %void None %4",\n          "%8 = OpLabel",\n          "%9 = OpIMul %int %int_16 %int_5",\n               "OpReturn",\n               "OpFunctionEnd"\n      // clang-format on\n  };\n\n  auto result = SinglePassRunAndDisassemble<opt::StrengthReductionPass>(\n      JoinAllInsts(text), /* skip_nop = */ true);\n\n  EXPECT_EQ(opt::Pass::Status::SuccessWithChange, std::get<1>(result));\n  const std::string& output = std::get<0>(result);\n  EXPECT_THAT(output, Not(HasSubstr("OpIMul")));\n  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %int %int_5 %uint_4"));\n}\n\n// Test to make sure we replace a multiple of 32 and 4.\nTEST_F(StrengthReductionBasicTest, BasicTwoPowersOf2) {\n  // one of them for the bit shift.\n  // clang-format off\n  const std::string text = R"(\n          OpCapability Shader\n     %1 = OpExtInstImport "GLSL.std.450"\n          OpMemoryModel Logical GLSL450\n          OpEntryPoint Vertex %main "main"\n          OpName %main "main"\n  %void = OpTypeVoid\n     %4 = OpTypeFunction %void\n   %int = OpTypeInt 32 1\n%int_32 = OpConstant %int 32\n %int_4 = OpConstant %int 4\n  %main = OpFunction %void None %4\n     %8 = OpLabel\n     %9 = OpIMul %int %int_32 %int_4\n          OpReturn\n          OpFunctionEnd\n)";\n  // clang-format on\n  auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(\n      text, /* skip_nop = */ true, /* do_validation = */ false);\n\n  EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));\n  const std::string& output = std::get<0>(result);\n  EXPECT_THAT(output, Not(HasSubstr("OpIMul")));\n  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %int %int_4 %uint_5"));\n}\n\n// Test to make sure we don\'t replace 0*5.\nTEST_F(StrengthReductionBasicTest, BasicDontReplace0) {\n  const std::vector<const char*> text = {\n      // clang-format off\n               "OpCapability Shader",\n          "%1 = OpExtInstImport \\"GLSL.std.450\\"",\n               "OpMemoryModel Logical GLSL450",\n               "OpEntryPoint Vertex %main \\"main\\"",\n               "OpName %main \\"main\\"",\n       "%void = OpTypeVoid",\n          "%4 = OpTypeFunction %void",\n        "%int = OpTypeInt 32 1",\n      "%int_0 = OpConstant %int 0",\n      "%int_5 = OpConstant %int 5",\n       "%main = OpFunction %void None %4",\n          "%8 = OpLabel",\n          "%9 = OpIMul %int %int_0 %int_5",\n               "OpReturn",\n               "OpFunctionEnd"\n      // clang-format on\n  };\n\n  auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(\n      JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);\n\n  EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));\n}\n\n// Test to make sure we do not replace a multiple of 5 and 7.\nTEST_F(StrengthReductionBasicTest, BasicNoChange) {\n  const std::vector<const char*> text = {\n      // clang-format off\n             "OpCapability Shader",\n        "%1 = OpExtInstImport \\"GLSL.std.450\\"",\n             "OpMemoryModel Logical GLSL450",\n             "OpEntryPoint Vertex %2 \\"main\\"",\n             "OpName %2 \\"main\\"",\n        "%3 = OpTypeVoid",\n        "%4 = OpTypeFunction %3",\n        "%5 = OpTypeInt 32 1",\n        "%6 = OpTypeInt 32 0",\n        "%7 = OpConstant %5 5",\n        "%8 = OpConstant %5 7",\n        "%2 = OpFunction %3 None %4",\n        "%9 = OpLabel",\n        "%10 = OpIMul %5 %7 %8",\n             "OpReturn",\n             "OpFunctionEnd",\n      // clang-format on\n  };\n\n  auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(\n      JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);\n\n  EXPECT_EQ(Pass::Status::SuccessWithoutChange, std::get<1>(result));\n}\n\n// Test to make sure constants and types are reused and not duplicated.\nTEST_F(StrengthReductionBasicTest, NoDuplicateConstantsAndTypes) {\n  const std::vector<const char*> text = {\n      // clang-format off\n               "OpCapability Shader",\n          "%1 = OpExtInstImport \\"GLSL.std.450\\"",\n               "OpMemoryModel Logical GLSL450",\n               "OpEntryPoint Vertex %main \\"main\\"",\n               "OpName %main \\"main\\"",\n       "%void = OpTypeVoid",\n          "%4 = OpTypeFunction %void",\n       "%uint = OpTypeInt 32 0",\n     "%uint_8 = OpConstant %uint 8",\n     "%uint_3 = OpConstant %uint 3",\n       "%main = OpFunction %void None %4",\n          "%8 = OpLabel",\n          "%9 = OpIMul %uint %uint_8 %uint_3",\n               "OpReturn",\n               "OpFunctionEnd",\n      // clang-format on\n  };\n\n  auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(\n      JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);\n\n  EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));\n  const std::string& output = std::get<0>(result);\n  EXPECT_THAT(output,\n              Not(MatchesRegex(".*OpConstant %uint 3.*OpConstant %uint 3.*")));\n  EXPECT_THAT(output, Not(MatchesRegex(".*OpTypeInt 32 0.*OpTypeInt 32 0.*")));\n}\n\n// Test to make sure we generate the constants only once\nTEST_F(StrengthReductionBasicTest, BasicCreateOneConst) {\n  const std::vector<const char*> text = {\n      // clang-format off\n               "OpCapability Shader",\n          "%1 = OpExtInstImport \\"GLSL.std.450\\"",\n               "OpMemoryModel Logical GLSL450",\n               "OpEntryPoint Vertex %main \\"main\\"",\n               "OpName %main \\"main\\"",\n       "%void = OpTypeVoid",\n          "%4 = OpTypeFunction %void",\n       "%uint = OpTypeInt 32 0",\n     "%uint_5 = OpConstant %uint 5",\n     "%uint_9 = OpConstant %uint 9",\n   "%uint_128 = OpConstant %uint 128",\n       "%main = OpFunction %void None %4",\n          "%8 = OpLabel",\n          "%9 = OpIMul %uint %uint_5 %uint_128",\n         "%10 = OpIMul %uint %uint_9 %uint_128",\n               "OpReturn",\n               "OpFunctionEnd"\n      // clang-format on\n  };\n\n  auto result = SinglePassRunAndDisassemble<StrengthReductionPass>(\n      JoinAllInsts(text), /* skip_nop = */ true, /* do_validation = */ false);\n\n  EXPECT_EQ(Pass::Status::SuccessWithChange, std::get<1>(result));\n  const std::string& output = std::get<0>(result);\n  EXPECT_THAT(output, Not(HasSubstr("OpIMul")));\n  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %uint %uint_5 %uint_7"));\n  EXPECT_THAT(output, HasSubstr("OpShiftLeftLogical %uint %uint_9 %uint_7"));\n}\n\n// Test to make sure we generate the instructions in the correct position and\n// that the uses get replaced as well.  Here we check that the use in the return\n// is replaced, we also check that we can replace two OpIMuls when one feeds the\n// other.\nTEST_F(StrengthReductionBasicTest, BasicCheckPositionAndReplacement) {\n  // This is just the preamble to set up the test.\n  const std::vector<const char*> common_text = {\n      // clang-format off\n               "OpCapability Shader",\n          "%1 = OpExtInstImport \\"GLSL.std.450\\"",\n               "OpMemoryModel Logical GLSL450",\n               "OpEntryPoint Fragment %main \\"main\\" %gl_FragColor",\n               "OpExecutionMode %main OriginUpperLeft",\n               "OpName %main \\"main\\"",\n               "OpName %foo_i1_ \\"foo(i1;\\"",\n               "OpName %n \\"n\\"",\n               "OpName %gl_FragColor \\"gl_FragColor\\"",\n               "OpName %param \\"param\\"",\n               "OpDecorate %gl_FragColor Location 0",\n       "%void = OpTypeVoid",\n          "%3 = OpTypeFunction %void",\n        "%int = OpTypeInt 32 1",\n"%_ptr_Function_int = OpTypePointer Function %int",\n          "%8 = OpTypeFunction %int %_ptr_Function_int",\n    "%int_256 = OpConstant %int 256",\n      "%int_2 = OpConstant %int 2",\n      "%float = OpTypeFloat 32",\n    "%v4float = OpTypeVector %float 4",\n"%_ptr_Output_v4float = OpTypePointer Output %v4float",\n"%gl_FragColor = OpVariable %_ptr_Output_v4float Output",\n    "%float_1 = OpConstant %float 1",\n     "%int_10 = OpConstant %int 10",\n  "%float_0_375 = OpConstant %float 0.375",\n  "%float_0_75 = OpConstant %float 0.75",\n       "%uint = OpTypeInt 32 0",\n     "%uint_8 = OpConstant %uint 8",\n     "%uint_1 = OpConstant %uint 1",\n       "%main = OpFunction %void None %3",\n          "%5 = OpLabel",\n      "%param = OpVariable %_ptr_Function_int Function",\n               "OpStore %param %int_10",\n         "%26 = OpFunctionCall %int %foo_i1_ %param",\n         "%27 = OpConvertSToF %float %26",\n         "%28 = OpFDiv %float %float_1 %27",\n         "%31 = OpCompositeConstruct %v4float %28 %float_0_375 %float_0_75 %float_1",\n               "OpStore %gl_FragColor %31",\n               "OpReturn",\n               "OpFunctionEnd"\n      // clang-format on\n  };\n\n  // This is the real test.  The two OpIMul should be replaced.  The expected\n  // output is in |foo_after|.\n  const std::vector<const char*> foo_before = {\n      // clang-format off\n    "%foo_i1_ = OpFunction %int None %8",\n          "%n = OpFunctionParameter %_ptr_Function_int",\n         "%11 = OpLabel",\n         "%12 = OpLoad %int %n",\n         "%14 = OpIMul %int %12 %int_256",\n         "%16 = OpIMul %int %14 %int_2",\n               "OpReturnValue %16",\n               "OpFunctionEnd",\n\n      // clang-format on\n  };\n\n  const std::vector<const char*> foo_after = {\n      // clang-format off\n    "%foo_i1_ = OpFunction %int None %8",\n          "%n = OpFunctionParameter %_ptr_Function_int",\n         "%11 = OpLabel",\n         "%12 = OpLoad %int %n",\n         "%33 = OpShiftLeftLogical %int %12 %uint_8",\n         "%34 = OpShiftLeftLogical %int %33 %uint_1",\n               "OpReturnValue %34",\n               "OpFunctionEnd",\n      // clang-format on\n  };\n\n  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);\n  SinglePassRunAndCheck<StrengthReductionPass>(\n      JoinAllInsts(Concat(common_text, foo_before)),\n      JoinAllInsts(Concat(common_text, foo_after)),\n      /* skip_nop = */ true, /* do_validate = */ true);\n}\n\n// Test that, when the result of an OpIMul instruction has more than 1 use, and\n// the instruction is replaced, all of the uses of the results are replace with\n// the new result.\nTEST_F(StrengthReductionBasicTest, BasicTestMultipleReplacements) {\n  // This is just the preamble to set up the test.\n  const std::vector<const char*> common_text = {\n      // clang-format off\n               "OpCapability Shader",\n          "%1 = OpExtInstImport \\"GLSL.std.450\\"",\n               "OpMemoryModel Logical GLSL450",\n               "OpEntryPoint Fragment %main \\"main\\" %gl_FragColor",\n               "OpExecutionMode %main OriginUpperLeft",\n               "OpName %main \\"main\\"",\n               "OpName %foo_i1_ \\"foo(i1;\\"",\n               "OpName %n \\"n\\"",\n               "OpName %gl_FragColor \\"gl_FragColor\\"",\n               "OpName %param \\"param\\"",\n               "OpDecorate %gl_FragColor Location 0",\n       "%void = OpTypeVoid",\n          "%3 = OpTypeFunction %void",\n        "%int = OpTypeInt 32 1",\n"%_ptr_Function_int = OpTypePointer Function %int",\n          "%8 = OpTypeFunction %int %_ptr_Function_int",\n    "%int_256 = OpConstant %int 256",\n      "%int_2 = OpConstant %int 2",\n      "%float = OpTypeFloat 32",\n    "%v4float = OpTypeVector %float 4",\n"%_ptr_Output_v4float = OpTypePointer Output %v4float",\n"%gl_FragColor = OpVariable %_ptr_Output_v4float Output",\n    "%float_1 = OpConstant %float 1",\n     "%int_10 = OpConstant %int 10",\n  "%float_0_375 = OpConstant %float 0.375",\n  "%float_0_75 = OpConstant %float 0.75",\n       "%uint = OpTypeInt 32 0",\n     "%uint_8 = OpConstant %uint 8",\n     "%uint_1 = OpConstant %uint 1",\n       "%main = OpFunction %void None %3",\n          "%5 = OpLabel",\n      "%param = OpVariable %_ptr_Function_int Function",\n               "OpStore %param %int_10",\n         "%26 = OpFunctionCall %int %foo_i1_ %param",\n         "%27 = OpConvertSToF %float %26",\n         "%28 = OpFDiv %float %float_1 %27",\n         "%31 = OpCompositeConstruct %v4float %28 %float_0_375 %float_0_75 %float_1",\n               "OpStore %gl_FragColor %31",\n               "OpReturn",\n               "OpFunctionEnd"\n      // clang-format on\n  };\n\n  // This is the real test.  The two OpIMul instructions should be replaced.  In\n  // particular, we want to be sure that both uses of %16 are changed to use the\n  // new result.\n  const std::vector<const char*> foo_before = {\n      // clang-format off\n    "%foo_i1_ = OpFunction %int None %8",\n          "%n = OpFunctionParameter %_ptr_Function_int",\n         "%11 = OpLabel",\n         "%12 = OpLoad %int %n",\n         "%14 = OpIMul %int %12 %int_256",\n         "%16 = OpIMul %int %14 %int_2",\n         "%17 = OpIAdd %int %14 %16",\n               "OpReturnValue %17",\n               "OpFunctionEnd",\n\n      // clang-format on\n  };\n\n  const std::vector<const char*> foo_after = {\n      // clang-format off\n    "%foo_i1_ = OpFunction %int None %8",\n          "%n = OpFunctionParameter %_ptr_Function_int",\n         "%11 = OpLabel",\n         "%12 = OpLoad %int %n",\n         "%34 = OpShiftLeftLogical %int %12 %uint_8",\n         "%35 = OpShiftLeftLogical %int %34 %uint_1",\n         "%17 = OpIAdd %int %34 %35",\n               "OpReturnValue %17",\n               "OpFunctionEnd",\n      // clang-format on\n  };\n\n  SetAssembleOptions(SPV_TEXT_TO_BINARY_OPTION_PRESERVE_NUMERIC_IDS);\n  SinglePassRunAndCheck<StrengthReductionPass>(\n      JoinAllInsts(Concat(common_text, foo_before)),\n      JoinAllInsts(Concat(common_text, foo_after)),\n      /* skip_nop = */ true, /* do_validate = */ true);\n}\n\n}  // namespace\n}  // namespace opt\n}  // namespace spvtools\n', 'message': "Tests: Add optional dependency on Effcee stateful matcher\n\nAdd Effcee as an optional dependency for use in tests.  In future it will\nbe a required dependency.\n\nEffcee is a stateful pattern matcher that has much of the functionality\nof LLVM's FileCheck, except in library form.  Effcee makes it much easier\nto write tests for optimization passes.\n\nDemonstrate its use in a test for the strength-reduction pass.\n\nUpdate README.md with example commands of how to get sources.\n\nUpdate Appveyor and Travis-CI build rules.\n\nAlso: Include test libraries if not SPIRV_SKIP_TESTS\n- SPIRV_SKIP_TESTS is implied by SPIRV_SKIP_EXECUTABLES\n", 'author_name': 'David Neto', 'lang': 'cpp'}