Quelle  constant_folding_test.cc

/*
 * Copyright (C) 2014 The Android Open Source Project
 *
 * 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 <functional>

#include "constant_folding.h"

#include "art_field-inl.h"
#include "class_linker.h"
#include "base/macros.h"
#include "dead_code_elimination.h"
#include "driver/compiler_options.h"
#include "graph_checker.h"
#include "handle_scope-inl.h"
#include "mirror/class-inl.h"
#include "optimizing_unit_test.h"
#include "pretty_printer.h"
#include "scoped_thread_state_change.h"
#include "thread.h"

#include "gtest/gtest.h"

namespace art HIDDEN {

/**
 * Fixture class for the constant folding and dce tests.
 */
class ConstantFoldingTest : public CommonCompilerTest, public OptimizingUnitTestHelper {
 public:
  ConstantFoldingTest() { }

  void TestCode(const std::vector<uint16_t>& data,
                const std::string& expected_before,
                const std::string& expected_after_cf,
                const std::string& expected_after_dce,
                const std::function<void(HGraph*)>& check_after_cf,
                DataType::Type return_type = DataType::Type::kInt32) {
    graph_ = CreateCFG(data, return_type);
    TestCodeOnReadyGraph(expected_before,
                         expected_after_cf,
                         expected_after_dce,
                         check_after_cf);
  }

  void TestCodeOnReadyGraph(const std::string& expected_before,
                            const std::string& expected_after_cf,
                            const std::string& expected_after_dce,
                            const std::function<void(HGraph*)>& check_after_cf) {
    ASSERT_NE(graph_, nullptr);

    StringPrettyPrinter printer_before(graph_);
    printer_before.VisitInsertionOrder();
    std::string actual_before = printer_before.str();
    EXPECT_EQ(expected_before, actual_before);

    HConstantFolding(graph_, *compiler_options_, /* stats= */ nullptr, "constant_folding").Run();
    GraphChecker graph_checker_cf(graph_);
    graph_checker_cf.Run();
    ASSERT_TRUE(graph_checker_cf.IsValid());

    StringPrettyPrinter printer_after_cf(graph_);
    printer_after_cf.VisitInsertionOrder();
    std::string actual_after_cf = printer_after_cf.str();
    EXPECT_EQ(expected_after_cf, actual_after_cf);

    check_after_cf(graph_);

    HDeadCodeElimination(graph_, /* stats= */ nullptr, "dead_code_elimination").Run();
    GraphChecker graph_checker_dce(graph_);
    graph_checker_dce.Run();
    ASSERT_TRUE(graph_checker_dce.IsValid());

    StringPrettyPrinter printer_after_dce(graph_);
    printer_after_dce.VisitInsertionOrder();
    std::string actual_after_dce = printer_after_dce.str();
    EXPECT_EQ(expected_after_dce, actual_after_dce);
  }
};

/**
 * Tiny three-register program exercising int constant folding on negation.
 *
 *                              16-bit
 *                              offset
 *                              ------
 *     v0 <- 1                  0.      const/4 v0, #+1
 *     v1 <- -v0                1.      neg-int v1, v0
 *     return v1                2.      return v1
 */
TEST_F(ConstantFoldingTest, IntConstantFoldingNegation) {
  const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM(
    Instruction::CONST_4 | 0 << 8 | 1 << 12,
    Instruction::NEG_INT | 1 << 8 | 0 << 12,
    Instruction::RETURN | 1 << 8);

  std::string expected_before =
      "BasicBlock 0, succ: 1\n"
      "  2: IntConstant [3]\n"
      "  0: SuspendCheck\n"
      "  1: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 2\n"
      "  3: Neg(2) [4]\n"
      "  4: Return(3)\n"
      "BasicBlock 2, pred: 1\n"
      "  5: Exit\n";

  // Expected difference after constant folding.
  diff_t expected_cf_diff = {
    { "  2: IntConstant [3]\n", "  2: IntConstant\n"
                                "  6: IntConstant [4]\n" },
    { "  3: Neg(2) [4]\n",      removed },
    { "  4: Return(3)\n",       "  4: Return(6)\n" }
  };
  std::string expected_after_cf = Patch(expected_before, expected_cf_diff);

  // Check the value of the computed constant.
  auto check_after_cf = [](HGraph* graph) {
    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
    ASSERT_TRUE(inst->IsIntConstant());
    ASSERT_EQ(inst->AsIntConstant()->GetValue(), -1);
  };

  // Expected difference after dead code elimination.
  diff_t expected_dce_diff = {
    { "  2: IntConstant\n", removed },
  };
  std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);

  TestCode(data,
           expected_before,
           expected_after_cf,
           expected_after_dce,
           check_after_cf);
}

/**
 * Tiny three-register program exercising long constant folding on negation.
 *
 *                              16-bit
 *                              offset
 *                              ------
 *     (v0, v1) <- 4294967296   0.      const-wide v0 #+4294967296
 *     (v2, v3) <- -(v0, v1)    1.      neg-long v2, v0
 *     return (v2, v3)          2.      return-wide v2
 */
TEST_F(ConstantFoldingTest, LongConstantFoldingNegation) {
  const int64_t input = INT64_C(4294967296);             // 2^32
  const uint16_t word0 = Low16Bits(Low32Bits(input));    // LSW.
  const uint16_t word1 = High16Bits(Low32Bits(input));
  const uint16_t word2 = Low16Bits(High32Bits(input));
  const uint16_t word3 = High16Bits(High32Bits(input));  // MSW.
  const std::vector<uint16_t> data = FOUR_REGISTERS_CODE_ITEM(
    Instruction::CONST_WIDE | 0 << 8, word0, word1, word2, word3,
    Instruction::NEG_LONG | 2 << 8 | 0 << 12,
    Instruction::RETURN_WIDE | 2 << 8);

  std::string expected_before =
      "BasicBlock 0, succ: 1\n"
      "  2: LongConstant [3]\n"
      "  0: SuspendCheck\n"
      "  1: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 2\n"
      "  3: Neg(2) [4]\n"
      "  4: Return(3)\n"
      "BasicBlock 2, pred: 1\n"
      "  5: Exit\n";

  // Expected difference after constant folding.
  diff_t expected_cf_diff = {
    { "  2: LongConstant [3]\n", "  2: LongConstant\n"
                                 "  6: LongConstant [4]\n" },
    { "  3: Neg(2) [4]\n",       removed },
    { "  4: Return(3)\n",        "  4: Return(6)\n" }
  };
  std::string expected_after_cf = Patch(expected_before, expected_cf_diff);

  // Check the value of the computed constant.
  auto check_after_cf = [](HGraph* graph) {
    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
    ASSERT_TRUE(inst->IsLongConstant());
    ASSERT_EQ(inst->AsLongConstant()->GetValue(), INT64_C(-4294967296));
  };

  // Expected difference after dead code elimination.
  diff_t expected_dce_diff = {
    { "  2: LongConstant\n", removed },
  };
  std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);

  TestCode(data,
           expected_before,
           expected_after_cf,
           expected_after_dce,
           check_after_cf,
           DataType::Type::kInt64);
}

/**
 * Tiny three-register program exercising int constant folding on addition.
 *
 *                              16-bit
 *                              offset
 *                              ------
 *     v0 <- 1                  0.      const/4 v0, #+1
 *     v1 <- 2                  1.      const/4 v1, #+2
 *     v2 <- v0 + v1            2.      add-int v2, v0, v1
 *     return v2                4.      return v2
 */
TEST_F(ConstantFoldingTest, IntConstantFoldingOnAddition1) {
  const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
    Instruction::CONST_4 | 0 << 8 | 1 << 12,
    Instruction::CONST_4 | 1 << 8 | 2 << 12,
    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
    Instruction::RETURN | 2 << 8);

  std::string expected_before =
      "BasicBlock 0, succ: 1\n"
      "  2: IntConstant [4]\n"
      "  3: IntConstant [4]\n"
      "  0: SuspendCheck\n"
      "  1: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 2\n"
      "  4: Add(2, 3) [5]\n"
      "  5: Return(4)\n"
      "BasicBlock 2, pred: 1\n"
      "  6: Exit\n";

  // Expected difference after constant folding.
  diff_t expected_cf_diff = {
    { "  2: IntConstant [4]\n", "  2: IntConstant\n" },
    { "  3: IntConstant [4]\n", "  3: IntConstant\n"
                                "  7: IntConstant [5]\n" },
    { "  4: Add(2, 3) [5]\n",   removed },
    { "  5: Return(4)\n",       "  5: Return(7)\n" }
  };
  std::string expected_after_cf = Patch(expected_before, expected_cf_diff);

  // Check the value of the computed constant.
  auto check_after_cf = [](HGraph* graph) {
    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
    ASSERT_TRUE(inst->IsIntConstant());
    ASSERT_EQ(inst->AsIntConstant()->GetValue(), 3);
  };

  // Expected difference after dead code elimination.
  diff_t expected_dce_diff = {
    { "  2: IntConstant\n", removed },
    { "  3: IntConstant\n", removed }
  };
  std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);

  TestCode(data,
           expected_before,
           expected_after_cf,
           expected_after_dce,
           check_after_cf);
}

/**
 * Small three-register program exercising int constant folding on addition.
 *
 *                              16-bit
 *                              offset
 *                              ------
 *     v0 <- 1                  0.      const/4 v0, #+1
 *     v1 <- 2                  1.      const/4 v1, #+2
 *     v0 <- v0 + v1            2.      add-int/2addr v0, v1
 *     v1 <- 4                  3.      const/4 v1, #+4
 *     v2 <- 5                  4.      const/4 v2, #+5
 *     v1 <- v1 + v2            5.      add-int/2addr v1, v2
 *     v2 <- v0 + v1            6.      add-int v2, v0, v1
 *     return v2                8.      return v2
 */
TEST_F(ConstantFoldingTest, IntConstantFoldingOnAddition2) {
  const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
    Instruction::CONST_4 | 0 << 8 | 1 << 12,
    Instruction::CONST_4 | 1 << 8 | 2 << 12,
    Instruction::ADD_INT_2ADDR | 0 << 8 | 1 << 12,
    Instruction::CONST_4 | 1 << 8 | 4 << 12,
    Instruction::CONST_4 | 2 << 8 | 5 << 12,
    Instruction::ADD_INT_2ADDR | 1 << 8 | 2 << 12,
    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
    Instruction::RETURN | 2 << 8);

  std::string expected_before =
      "BasicBlock 0, succ: 1\n"
      "  2: IntConstant [4]\n"
      "  3: IntConstant [4]\n"
      "  5: IntConstant [7]\n"
      "  6: IntConstant [7]\n"
      "  0: SuspendCheck\n"
      "  1: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 2\n"
      "  4: Add(2, 3) [8]\n"
      "  7: Add(5, 6) [8]\n"
      "  8: Add(4, 7) [9]\n"
      "  9: Return(8)\n"
      "BasicBlock 2, pred: 1\n"
      "  10: Exit\n";

  // Expected difference after constant folding.
  diff_t expected_cf_diff = {
    { "  2: IntConstant [4]\n",  "  2: IntConstant\n" },
    { "  3: IntConstant [4]\n",  "  3: IntConstant\n" },
    { "  5: IntConstant [7]\n",  "  5: IntConstant\n" },
    { "  6: IntConstant [7]\n",  "  6: IntConstant\n"
                                 "  11: IntConstant\n"
                                 "  12: IntConstant\n"
                                 "  13: IntConstant [9]\n" },
    { "  4: Add(2, 3) [8]\n",    removed },
    { "  7: Add(5, 6) [8]\n",    removed },
    { "  8: Add(4, 7) [9]\n",    removed  },
    { "  9: Return(8)\n",        "  9: Return(13)\n" }
  };
  std::string expected_after_cf = Patch(expected_before, expected_cf_diff);

  // Check the values of the computed constants.
  auto check_after_cf = [](HGraph* graph) {
    HInstruction* inst1 = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
    ASSERT_TRUE(inst1->IsIntConstant());
    ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 12);
    HInstruction* inst2 = inst1->GetPrevious();
    ASSERT_TRUE(inst2->IsIntConstant());
    ASSERT_EQ(inst2->AsIntConstant()->GetValue(), 9);
    HInstruction* inst3 = inst2->GetPrevious();
    ASSERT_TRUE(inst3->IsIntConstant());
    ASSERT_EQ(inst3->AsIntConstant()->GetValue(), 3);
  };

  // Expected difference after dead code elimination.
  diff_t expected_dce_diff = {
    { "  2: IntConstant\n",  removed },
    { "  3: IntConstant\n",  removed },
    { "  5: IntConstant\n",  removed },
    { "  6: IntConstant\n",  removed },
    { "  11: IntConstant\n", removed },
    { "  12: IntConstant\n", removed }
  };
  std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);

  TestCode(data,
           expected_before,
           expected_after_cf,
           expected_after_dce,
           check_after_cf);
}

/**
 * Tiny three-register program exercising int constant folding on subtraction.
 *
 *                              16-bit
 *                              offset
 *                              ------
 *     v0 <- 3                  0.      const/4 v0, #+3
 *     v1 <- 2                  1.      const/4 v1, #+2
 *     v2 <- v0 - v1            2.      sub-int v2, v0, v1
 *     return v2                4.      return v2
 */
TEST_F(ConstantFoldingTest, IntConstantFoldingOnSubtraction) {
  const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
    Instruction::CONST_4 | 0 << 8 | 3 << 12,
    Instruction::CONST_4 | 1 << 8 | 2 << 12,
    Instruction::SUB_INT | 2 << 8, 0 | 1 << 8,
    Instruction::RETURN | 2 << 8);

  std::string expected_before =
      "BasicBlock 0, succ: 1\n"
      "  2: IntConstant [4]\n"
      "  3: IntConstant [4]\n"
      "  0: SuspendCheck\n"
      "  1: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 2\n"
      "  4: Sub(2, 3) [5]\n"
      "  5: Return(4)\n"
      "BasicBlock 2, pred: 1\n"
      "  6: Exit\n";

  // Expected difference after constant folding.
  diff_t expected_cf_diff = {
    { "  2: IntConstant [4]\n",  "  2: IntConstant\n" },
    { "  3: IntConstant [4]\n",  "  3: IntConstant\n"
                                 "  7: IntConstant [5]\n" },
    { "  4: Sub(2, 3) [5]\n",    removed },
    { "  5: Return(4)\n",        "  5: Return(7)\n" }
  };
  std::string expected_after_cf = Patch(expected_before, expected_cf_diff);

  // Check the value of the computed constant.
  auto check_after_cf = [](HGraph* graph) {
    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
    ASSERT_TRUE(inst->IsIntConstant());
    ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1);
  };

  // Expected difference after dead code elimination.
  diff_t expected_dce_diff = {
    { "  2: IntConstant\n", removed },
    { "  3: IntConstant\n", removed }
  };
  std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);

  TestCode(data,
           expected_before,
           expected_after_cf,
           expected_after_dce,
           check_after_cf);
}

/**
 * Tiny three-register-pair program exercising long constant folding
 * on addition.
 *
 *                              16-bit
 *                              offset
 *                              ------
 *     (v0, v1) <- 1            0.      const-wide/16 v0, #+1
 *     (v2, v3) <- 2            2.      const-wide/16 v2, #+2
 *     (v4, v5) <-
 *       (v0, v1) + (v1, v2)    4.      add-long v4, v0, v2
 *     return (v4, v5)          6.      return-wide v4
 */
TEST_F(ConstantFoldingTest, LongConstantFoldingOnAddition) {
  const std::vector<uint16_t> data = SIX_REGISTERS_CODE_ITEM(
    Instruction::CONST_WIDE_16 | 0 << 8, 1,
    Instruction::CONST_WIDE_16 | 2 << 8, 2,
    Instruction::ADD_LONG | 4 << 8, 0 | 2 << 8,
    Instruction::RETURN_WIDE | 4 << 8);

  std::string expected_before =
      "BasicBlock 0, succ: 1\n"
      "  2: LongConstant [4]\n"
      "  3: LongConstant [4]\n"
      "  0: SuspendCheck\n"
      "  1: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 2\n"
      "  4: Add(2, 3) [5]\n"
      "  5: Return(4)\n"
      "BasicBlock 2, pred: 1\n"
      "  6: Exit\n";

  // Expected difference after constant folding.
  diff_t expected_cf_diff = {
    { "  2: LongConstant [4]\n",  "  2: LongConstant\n" },
    { "  3: LongConstant [4]\n",  "  3: LongConstant\n"
                                  "  7: LongConstant [5]\n" },
    { "  4: Add(2, 3) [5]\n",     removed },
    { "  5: Return(4)\n",         "  5: Return(7)\n" }
  };
  std::string expected_after_cf = Patch(expected_before, expected_cf_diff);

  // Check the value of the computed constant.
  auto check_after_cf = [](HGraph* graph) {
    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
    ASSERT_TRUE(inst->IsLongConstant());
    ASSERT_EQ(inst->AsLongConstant()->GetValue(), 3);
  };

  // Expected difference after dead code elimination.
  diff_t expected_dce_diff = {
    { "  2: LongConstant\n", removed },
    { "  3: LongConstant\n", removed }
  };
  std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);

  TestCode(data,
           expected_before,
           expected_after_cf,
           expected_after_dce,
           check_after_cf,
           DataType::Type::kInt64);
}

/**
 * Tiny three-register-pair program exercising long constant folding
 * on subtraction.
 *
 *                              16-bit
 *                              offset
 *                              ------
 *     (v0, v1) <- 3            0.      const-wide/16 v0, #+3
 *     (v2, v3) <- 2            2.      const-wide/16 v2, #+2
 *     (v4, v5) <-
 *       (v0, v1) - (v1, v2)    4.      sub-long v4, v0, v2
 *     return (v4, v5)          6.      return-wide v4
 */
TEST_F(ConstantFoldingTest, LongConstantFoldingOnSubtraction) {
  const std::vector<uint16_t> data = SIX_REGISTERS_CODE_ITEM(
    Instruction::CONST_WIDE_16 | 0 << 8, 3,
    Instruction::CONST_WIDE_16 | 2 << 8, 2,
    Instruction::SUB_LONG | 4 << 8, 0 | 2 << 8,
    Instruction::RETURN_WIDE | 4 << 8);

  std::string expected_before =
      "BasicBlock 0, succ: 1\n"
      "  2: LongConstant [4]\n"
      "  3: LongConstant [4]\n"
      "  0: SuspendCheck\n"
      "  1: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 2\n"
      "  4: Sub(2, 3) [5]\n"
      "  5: Return(4)\n"
      "BasicBlock 2, pred: 1\n"
      "  6: Exit\n";

  // Expected difference after constant folding.
  diff_t expected_cf_diff = {
    { "  2: LongConstant [4]\n",  "  2: LongConstant\n" },
    { "  3: LongConstant [4]\n",  "  3: LongConstant\n"
                                  "  7: LongConstant [5]\n" },
    { "  4: Sub(2, 3) [5]\n",     removed },
    { "  5: Return(4)\n",         "  5: Return(7)\n" }
  };
  std::string expected_after_cf = Patch(expected_before, expected_cf_diff);

  // Check the value of the computed constant.
  auto check_after_cf = [](HGraph* graph) {
    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
    ASSERT_TRUE(inst->IsLongConstant());
    ASSERT_EQ(inst->AsLongConstant()->GetValue(), 1);
  };

  // Expected difference after dead code elimination.
  diff_t expected_dce_diff = {
    { "  2: LongConstant\n", removed },
    { "  3: LongConstant\n", removed }
  };
  std::string expected_after_dce = Patch(expected_after_cf, expected_dce_diff);

  TestCode(data,
           expected_before,
           expected_after_cf,
           expected_after_dce,
           check_after_cf,
           DataType::Type::kInt64);
}

/**
 * Three-register program with jumps leading to the creation of many
 * blocks.
 *
 * The intent of this test is to ensure that all constant expressions
 * are actually evaluated at compile-time, thanks to the reverse
 * (forward) post-order traversal of the dominator tree.
 *
 *                              16-bit
 *                              offset
 *                              ------
 *     v0 <- 1                   0.     const/4 v0, #+1
 *     v1 <- 2                   1.     const/4 v1, #+2
 *     v2 <- v0 + v1             2.     add-int v2, v0, v1
 *     goto L2                   4.     goto +4
 * L1: v1 <- v0 + 5              5.     add-int/lit16 v1, v0, #+5
 *     goto L3                   7.     goto +4
 * L2: v0 <- v2 + 4              8.     add-int/lit16 v0, v2, #+4
 *     goto L1                  10.     goto +(-5)
 * L3: v2 <- v1 + 8             11.     add-int/lit16 v2, v1, #+8
 *     return v2                13.     return v2
 */
TEST_F(ConstantFoldingTest, IntConstantFoldingAndJumps) {
  const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
    Instruction::CONST_4 | 0 << 8 | 1 << 12,
    Instruction::CONST_4 | 1 << 8 | 2 << 12,
    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
    Instruction::GOTO | 4 << 8,
    Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 5,
    Instruction::GOTO | 4 << 8,
    Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 4,
    static_cast<uint16_t>(Instruction::GOTO | 0xFFFFFFFB << 8),
    Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 8,
    Instruction::RETURN | 2 << 8);

  std::string expected_before =
      "BasicBlock 0, succ: 1\n"
      "  2: IntConstant [4]\n"             // v0 <- 1
      "  3: IntConstant [4]\n"             // v1 <- 2
      "  6: IntConstant [7]\n"             // const 5
      "  9: IntConstant [10]\n"            // const 4
      "  12: IntConstant [13]\n"           // const 8
      "  0: SuspendCheck\n"
      "  1: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 3\n"
      "  4: Add(2, 3) [7]\n"               // v2 <- v0 + v1 = 1 + 2 = 3
      "  5: Goto 3\n"                      // goto L2
      "BasicBlock 2, pred: 3, succ: 4\n"   // L1:
      "  10: Add(7, 9) [13]\n"             // v1 <- v0 + 3 = 7 + 5 = 12
      "  11: Goto 4\n"                     // goto L3
      "BasicBlock 3, pred: 1, succ: 2\n"   // L2:
      "  7: Add(4, 6) [10]\n"              // v0 <- v2 + 2 = 3 + 4 = 7
      "  8: Goto 2\n"                      // goto L1
      "BasicBlock 4, pred: 2, succ: 5\n"   // L3:
      "  13: Add(10, 12) [14]\n"           // v2 <- v1 + 4 = 12 + 8 = 20
      "  14: Return(13)\n"                 // return v2
      "BasicBlock 5, pred: 4\n"
      "  15: Exit\n";

  // Expected difference after constant folding.
  diff_t expected_cf_diff = {
    { "  2: IntConstant [4]\n",   "  2: IntConstant\n" },
    { "  3: IntConstant [4]\n",   "  3: IntConstant\n" },
    { "  6: IntConstant [7]\n",   "  6: IntConstant\n" },
    { "  9: IntConstant [10]\n",  "  9: IntConstant\n" },
    { "  12: IntConstant [13]\n", "  12: IntConstant\n"
                                  "  16: IntConstant\n"
                                  "  17: IntConstant\n"
                                  "  18: IntConstant\n"
                                  "  19: IntConstant [14]\n" },
    { "  4: Add(2, 3) [7]\n",     removed },
    { "  10: Add(7, 9) [13]\n",   removed },
    { "  7: Add(4, 6) [10]\n",    removed },
    { "  13: Add(10, 12) [14]\n", removed },
    { "  14: Return(13)\n",       "  14: Return(19)\n"}
  };
  std::string expected_after_cf = Patch(expected_before, expected_cf_diff);

  // Check the values of the computed constants.
  auto check_after_cf = [](HGraph* graph) {
    HInstruction* inst1 = graph->GetBlocks()[4]->GetFirstInstruction()->InputAt(0);
    ASSERT_TRUE(inst1->IsIntConstant());
    ASSERT_EQ(inst1->AsIntConstant()->GetValue(), 20);
    HInstruction* inst2 = inst1->GetPrevious();
    ASSERT_TRUE(inst2->IsIntConstant());
    ASSERT_EQ(inst2->AsIntConstant()->GetValue(), 12);
    HInstruction* inst3 = inst2->GetPrevious();
    ASSERT_TRUE(inst3->IsIntConstant());
    ASSERT_EQ(inst3->AsIntConstant()->GetValue(), 7);
    HInstruction* inst4 = inst3->GetPrevious();
    ASSERT_TRUE(inst4->IsIntConstant());
    ASSERT_EQ(inst4->AsIntConstant()->GetValue(), 3);
  };

  // Expected difference after dead code elimination.
  std::string expected_after_dce =
      "BasicBlock 0, succ: 1\n"
      "  19: IntConstant [14]\n"
      "  0: SuspendCheck\n"
      "  1: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 5\n"
      "  14: Return(19)\n"
      "BasicBlock 5, pred: 1\n"
      "  15: Exit\n";

  TestCode(data,
           expected_before,
           expected_after_cf,
           expected_after_dce,
           check_after_cf);
}

/**
 * Three-register program with a constant (static) condition.
 *
 *                              16-bit
 *                              offset
 *                              ------
 *     v1 <- 1                  0.      const/4 v1, #+1
 *     v0 <- 0                  1.      const/4 v0, #+0
 *     if v1 >= 0 goto L1       2.      if-gez v1, +3
 *     v0 <- v1                 4.      move v0, v1
 * L1: v2 <- v0 + v1            5.      add-int v2, v0, v1
 *     return-void              7.      return
 */
TEST_F(ConstantFoldingTest, ConstantCondition) {
  const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
    Instruction::CONST_4 | 1 << 8 | 1 << 12,
    Instruction::CONST_4 | 0 << 8 | 0 << 12,
    Instruction::IF_GEZ | 1 << 8, 3,
    Instruction::MOVE | 0 << 8 | 1 << 12,
    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
    Instruction::RETURN_VOID);

  std::string expected_before =
      "BasicBlock 0, succ: 1\n"
      "  3: IntConstant [9, 8, 5]\n"
      "  4: IntConstant [8, 5]\n"
      "  1: SuspendCheck\n"
      "  2: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 5, 2\n"
      "  5: GreaterThanOrEqual(3, 4) [6]\n"
      "  6: If(5)\n"
      "BasicBlock 2, pred: 1, succ: 3\n"
      "  7: Goto 3\n"
      "BasicBlock 3, pred: 5, 2, succ: 4\n"
      "  8: Phi(4, 3) [9]\n"
      "  9: Add(8, 3)\n"
      "  10: ReturnVoid\n"
      "BasicBlock 4, pred: 3\n"
      "  11: Exit\n"
      "BasicBlock 5, pred: 1, succ: 3\n"
      "  0: Goto 3\n";

  // Expected difference after constant folding.
  diff_t expected_cf_diff = {
    { "  3: IntConstant [9, 8, 5]\n",        "  3: IntConstant [6, 9, 8]\n" },
    { "  4: IntConstant [8, 5]\n",           "  4: IntConstant [8]\n" },
    { "  5: GreaterThanOrEqual(3, 4) [6]\n", removed },
    { "  6: If(5)\n",                        "  6: If(3)\n" }
  };
  std::string expected_after_cf = Patch(expected_before, expected_cf_diff);

  // Check the values of the computed constants.
  auto check_after_cf = [](HGraph* graph) {
    HInstruction* inst = graph->GetBlocks()[1]->GetFirstInstruction()->InputAt(0);
    ASSERT_TRUE(inst->IsIntConstant());
    ASSERT_EQ(inst->AsIntConstant()->GetValue(), 1);
  };

  // Expected graph after dead code elimination.
  std::string expected_after_dce =
      "BasicBlock 0, succ: 1\n"
      "  1: SuspendCheck\n"
      "  2: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 4\n"
      "  10: ReturnVoid\n"
      "BasicBlock 4, pred: 1\n"
      "  11: Exit\n";

  TestCode(data,
           expected_before,
           expected_after_cf,
           expected_after_dce,
           check_after_cf);
}

/**
 * Unsigned comparisons with zero. Since these instructions are not present
 * in the bytecode, we need to set up the graph explicitly.
 */
TEST_F(ConstantFoldingTest, UnsignedComparisonsWithZero) {
  HBasicBlock* block = InitEntryMainExitGraph();

  // Make various unsigned comparisons with zero against a parameter.
  HInstruction* parameter = MakeParam(DataType::Type::kInt32);
  HInstruction* zero = graph_->GetIntConstant(0);

  HInstruction* a1 = MakeCondition(block, kCondA, zero, parameter);
  MakeSelect(block, a1, parameter, parameter);
  HInstruction* a2 = MakeCondition(block, kCondA, parameter, zero);
  MakeSelect(block, a2, parameter, parameter);
  HInstruction* ae1 = MakeCondition(block, kCondAE, zero, parameter);
  MakeSelect(block, ae1, parameter, parameter);
  HInstruction* ae2 = MakeCondition(block, kCondAE, parameter, zero);
  MakeSelect(block, ae2, parameter, parameter);
  HInstruction* b1 = MakeCondition(block, kCondB, zero, parameter);
  MakeSelect(block, b1, parameter, parameter);
  HInstruction* b2 = MakeCondition(block, kCondB, parameter, zero);
  MakeSelect(block, b2, parameter, parameter);
  HInstruction* be1 = MakeCondition(block, kCondBE, zero, parameter);
  MakeSelect(block, be1, parameter, parameter);
  HInstruction* be2 = MakeCondition(block, kCondBE, parameter, zero);
  MakeSelect(block, be2, parameter, parameter);
  MakeReturn(block, zero);

  graph_->BuildDominatorTree();

  const std::string expected_before =
      "BasicBlock 0, succ: 1\n"
      "  2: ParameterValue [19, 19, 18, 17, 17, 16, 15, 15, 14, 13, 13, 12, 11, 11, 10, "
                            "9, 9, 8, 7, 7, 6, 5, 5, 4]\n"
      "  3: IntConstant [20, 18, 16, 14, 12, 10, 8, 6, 4]\n"
      "  0: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 2\n"
      "  4: Above(3, 2) [5]\n"
      "  5: Select(2, 2, 4)\n"
      "  6: Above(2, 3) [7]\n"
      "  7: Select(2, 2, 6)\n"
      "  8: AboveOrEqual(3, 2) [9]\n"
      "  9: Select(2, 2, 8)\n"
      "  10: AboveOrEqual(2, 3) [11]\n"
      "  11: Select(2, 2, 10)\n"
      "  12: Below(3, 2) [13]\n"
      "  13: Select(2, 2, 12)\n"
      "  14: Below(2, 3) [15]\n"
      "  15: Select(2, 2, 14)\n"
      "  16: BelowOrEqual(3, 2) [17]\n"
      "  17: Select(2, 2, 16)\n"
      "  18: BelowOrEqual(2, 3) [19]\n"
      "  19: Select(2, 2, 18)\n"
      "  20: Return(3)\n"
      "BasicBlock 2, pred: 1\n"
      "  1: Exit\n";

  const std::string expected_after_cf =
      "BasicBlock 0, succ: 1\n"
      "  2: ParameterValue [19, 19, 18, 17, 17, 15, 15, 13, 13, 12, 11, 11, "
                            "9, 9, 8, 7, 7, 6, 5, 5]\n"
      "  3: IntConstant [15, 5, 20, 18, 12, 8, 6]\n"
      "  21: IntConstant [17, 11]\n"
      "  0: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 2\n"
      "  5: Select(2, 2, 3)\n"
      "  6: Above(2, 3) [7]\n"
      "  7: Select(2, 2, 6)\n"
      "  8: AboveOrEqual(3, 2) [9]\n"
      "  9: Select(2, 2, 8)\n"
      "  11: Select(2, 2, 21)\n"
      "  12: Below(3, 2) [13]\n"
      "  13: Select(2, 2, 12)\n"
      "  15: Select(2, 2, 3)\n"
      "  17: Select(2, 2, 21)\n"
      "  18: BelowOrEqual(2, 3) [19]\n"
      "  19: Select(2, 2, 18)\n"
      "  20: Return(3)\n"
      "BasicBlock 2, pred: 1\n"
      "  1: Exit\n";

  const std::string expected_after_dce =
      "BasicBlock 0, succ: 1\n"
      "  2: ParameterValue\n"
      "  3: IntConstant [20]\n"
      "  0: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 2\n"
      "  20: Return(3)\n"
      "BasicBlock 2, pred: 1\n"
      "  1: Exit\n";

  auto check_after_cf = [](HGraph* graph) {
    CHECK(graph != nullptr);
  };

  TestCodeOnReadyGraph(expected_before,
                       expected_after_cf,
                       expected_after_dce,
                       check_after_cf);
}

/**
 * Simple program with an integer static field get that has an assumed value override.
 */
TEST_F(ConstantFoldingTest, AssumeValueStaticFieldGetKnownValue) {
  ScopedObjectAccess soa(Thread::Current());
  VariableSizedHandleScope handles(soa.Self());

  // Fetch an arbitrary, known ArtField (java.lang.Integer.MAX_VALUE).
  ObjPtr<mirror::Class> integer_class =
      class_linker_->FindSystemClass(soa.Self(), "Ljava/lang/Integer;");
  ASSERT_FALSE(integer_class.IsNull());
  ASSERT_TRUE(integer_class->IsInitialized() || integer_class->IsInitializing());
  ArtField* field = integer_class->FindDeclaredStaticField("MAX_VALUE", "I");
  ASSERT_NE(field, nullptr) << "Could not find java.lang.Integer.MAX_VALUE";
  ASSERT_EQ(field->GetTypeAsPrimitiveType(), Primitive::kPrimInt);

  // Setup graph: Entry -> Main -> Exit
  // Main block will contain: LoadClass -> StaticFieldGet -> Return
  HBasicBlock* main_block = InitEntryMainExitGraph(&handles);
  HLoadClass* load_class = MakeLoadClass(main_block,
                                         integer_class->GetDexTypeIndex(),
                                         handles.NewHandle<mirror::Class>(integer_class));
  HStaticFieldGet* sget = MakeSFieldGet(main_block, load_class, field, DataType::Type::kInt32);
  MakeReturn(main_block, sget);
  graph_->BuildDominatorTree();

  // Override the assumed value for the ArtField, referenced during compilation.
  static constexpr int32_t kAssumedValueOverride = 12345;
  OverrideAssumedValue(field, kAssumedValueOverride);

  std::string expected_before =
      "BasicBlock 0, succ: 1\n"
      "  2: CurrentMethod [3]\n"
      "  0: Goto 1\n"
      "BasicBlock 1, pred: 0, succ: 2\n"
      "  3: LoadClass(2) [4]\n"
      "  4: StaticFieldGet(3) [5]\n"
      "  5: Return(4)\n"
      "BasicBlock 2, pred: 1\n"
      "  1: Exit\n";

  // Expected difference after constant folding.
  diff_t expected_cf_diff = {
      {"  2: CurrentMethod [3]\n",     "  2: CurrentMethod [3]\n"
                                       "  6: IntConstant [5]\n"},
      {"  3: LoadClass(2) [4]\n",      "  3: LoadClass(2)\n"},
      {"  4: StaticFieldGet(3) [5]\n", removed },
      {"  5: Return(4)\n",             "  5: Return(6)\n"},
  };
  std::string expected_after_cf = Patch(expected_before, expected_cf_diff);

  // Ensure the IntConstant reflects the override value.
  auto check_after_cf = [](HGraph* graph) {
    HInstruction* inst = graph->GetBlocks()[1]->GetLastInstruction()->InputAt(0);
    ASSERT_TRUE(inst->IsIntConstant());
    ASSERT_EQ(inst->AsIntConstant()->GetValue(), kAssumedValueOverride);
  };

  // We don't expect any meaningful differences after dead code elimination.
  std::string expected_after_dce = expected_after_cf;

  TestCodeOnReadyGraph(expected_before, expected_after_cf, expected_after_dce, check_after_cf);
}

TEST_F(ConstantFoldingTest, LoadConstantTableEntryWithConstantIndex) {
  HBasicBlock* block = InitEntryMainExitGraphWithReturnVoid();
  HInstruction* const1 = graph_->GetIntConstant(1);
  HInstruction* const2 = graph_->GetIntConstant(2);
  HInstruction* const3 = graph_->GetIntConstant(3);
  HInstruction* const4 = graph_->GetIntConstant(4);
  HLoadConstantTableEntry* lcte_double = MakeLoadConstantTableEntry(
      block, DataType::Type::kFloat64, const1, { 0.0, 1.0, 2.0, 3.0, 4.0, 5.0 });
  HLoadConstantTableEntry* lcte_float = MakeLoadConstantTableEntry(
      block, DataType::Type::kFloat32, const2, { 0.0f, -1.0f, -2.0f, -3.0f, -4.0f, -5.0f });
  HLoadConstantTableEntry* lcte_long = MakeLoadConstantTableEntry(
      block,
      DataType::Type::kInt64,
      const3,
      { INT64_C(0), INT64_C(1), INT64_C(2), INT64_C(3), INT64_C(4), INT64_C(5) });
  HLoadConstantTableEntry* lcte_int = MakeLoadConstantTableEntry(
      block, DataType::Type::kInt32, const4, { 0, 1, 2, 3, 4, 5 });
  HInvokeStaticOrDirect* invoke = MakeInvokeStatic(
      block, DataType::Type::kVoid, {lcte_double, lcte_float, lcte_long, lcte_int});

  graph_->BuildDominatorTree();
  HConstantFolding(graph_, *compiler_options_, /* stats= */ nullptr, "constant_folding").Run();

  ASSERT_INS_REMOVED(lcte_double);
  ASSERT_TRUE(invoke->InputAt(0)->IsDoubleConstant());
  ASSERT_EQ((bit_cast<uint64_t, double>(1.0)),
            invoke->InputAt(0)->AsDoubleConstant()->GetValueAsUint64());
  ASSERT_INS_REMOVED(lcte_float);
  ASSERT_TRUE(invoke->InputAt(1)->IsFloatConstant());
  ASSERT_EQ((bit_cast<uint32_t, float>(-2.0f)),
            invoke->InputAt(1)->AsFloatConstant()->GetValueAsUint64());
  ASSERT_INS_REMOVED(lcte_long);
  ASSERT_TRUE(invoke->InputAt(2)->IsLongConstant());
  ASSERT_EQ(INT64_C(3), invoke->InputAt(2)->AsLongConstant()->GetValue());
  ASSERT_INS_REMOVED(lcte_int);
  ASSERT_TRUE(invoke->InputAt(3)->IsIntConstant());
  ASSERT_EQ(4, invoke->InputAt(3)->AsIntConstant()->GetValue());
}

}  // namespace art