Introduce a class to implement optimization passes.

- Add art::HOptimization.
- Rename art::ConstantPropagation to art::HConstantFolding in
  compiler/optimizing/constant_folding.h to avoid name
  clashes with a class of the same name in
  compiler/dex/post_opt_passes.h.
- Rename art::DeadCodeElimination to
  art::HDeadCodeElimination for consistency reasons.
- Have art::HDeadCodeElimination and art::HConstantFolding
  derive from art::HOptimization.
- Start to use these optimizations in
  art:OptimizingCompiler::TryCompile.

Change-Id: Iaab350c122d87b2333b3760312b15c0592d7e010

1 files changed, 0 insertions, 487 deletions

diff --git a/compiler/optimizing/constant_propagation_test.cc b/compiler/optimizing/constant_propagation_test.cc
deleted file mode 100644
index 5c8c709439..0000000000
--- a/compiler/optimizing/constant_propagation_test.cc
+++ /dev/null
@@ -1,487 +0,0 @@
-/*
- * 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 "constant_propagation.h"
-#include "dead_code_elimination.h"
-#include "pretty_printer.h"
-#include "graph_checker.h"
-#include "optimizing_unit_test.h"
-
-#include "gtest/gtest.h"
-
-namespace art {
-
-static void TestCode(const uint16_t* data,
-                     const std::string& expected_before,
-                     const std::string& expected_after_cp,
-                     const std::string& expected_after_dce) {
-  ArenaPool pool;
-  ArenaAllocator allocator(&pool);
-  HGraph* graph = CreateCFG(&allocator, data);
-  ASSERT_NE(graph, nullptr);
-
-  graph->BuildDominatorTree();
-  graph->TransformToSSA();
-
-  StringPrettyPrinter printer_before(graph);
-  printer_before.VisitInsertionOrder();
-  std::string actual_before = printer_before.str();
-  ASSERT_EQ(expected_before, actual_before);
-
-  ConstantPropagation(graph).Run();
-
-  StringPrettyPrinter printer_after_cp(graph);
-  printer_after_cp.VisitInsertionOrder();
-  std::string actual_after_cp = printer_after_cp.str();
-  ASSERT_EQ(expected_after_cp, actual_after_cp);
-
-  DeadCodeElimination(graph).Run();
-
-  StringPrettyPrinter printer_after_dce(graph);
-  printer_after_dce.VisitInsertionOrder();
-  std::string actual_after_dce = printer_after_dce.str();
-  ASSERT_EQ(expected_after_dce, actual_after_dce);
-
-  SSAChecker ssa_checker(&allocator, graph);
-  ssa_checker.VisitInsertionOrder();
-  ASSERT_TRUE(ssa_checker.IsValid());
-}
-
-
-/**
- * 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(ConstantPropagation, IntConstantFoldingOnAddition1) {
-  const 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"
-    "  3: IntConstant [9]\n"
-    "  5: IntConstant [9]\n"
-    "  14: SuspendCheck\n"
-    "  15: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  9: Add(3, 5) [12]\n"
-    "  12: Return(9)\n"
-    "BasicBlock 2, pred: 1\n"
-    "  13: Exit\n";
-
-  // Expected difference after constant propagation.
-  diff_t expected_cp_diff = {
-    { "  3: IntConstant [9]\n", "  3: IntConstant\n" },
-    { "  5: IntConstant [9]\n", "  5: IntConstant\n" },
-    { "  9: Add(3, 5) [12]\n",  "  16: IntConstant [12]\n" },
-    { "  12: Return(9)\n",      "  12: Return(16)\n" }
-  };
-  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
-
-  // Expected difference after dead code elimination.
-  diff_t expected_dce_diff = {
-    { "  3: IntConstant\n", removed },
-    { "  5: IntConstant\n", removed }
-  };
-  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
-
-  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
-}
-
-/**
- * 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 <- 3                  3.      const/4 v1, #+3
- *     v2 <- 4                  4.      const/4 v2, #+4
- *     v1 <- v1 + v2            5.      add-int/2addr v1, v2
- *     v2 <- v0 + v1            6.      add-int v2, v0, v1
- *     return v2                8.      return v2
- */
-TEST(ConstantPropagation, IntConstantFoldingOnAddition2) {
-  const 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 | 3 << 12,
-    Instruction::CONST_4 | 2 << 8 | 4 << 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"
-    "  3: IntConstant [9]\n"
-    "  5: IntConstant [9]\n"
-    "  11: IntConstant [17]\n"
-    "  13: IntConstant [17]\n"
-    "  26: SuspendCheck\n"
-    "  27: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  9: Add(3, 5) [21]\n"
-    "  17: Add(11, 13) [21]\n"
-    "  21: Add(9, 17) [24]\n"
-    "  24: Return(21)\n"
-    "BasicBlock 2, pred: 1\n"
-    "  25: Exit\n";
-
-  // Expected difference after constant propagation.
-  diff_t expected_cp_diff = {
-    { "  3: IntConstant [9]\n",   "  3: IntConstant\n" },
-    { "  5: IntConstant [9]\n",   "  5: IntConstant\n" },
-    { "  11: IntConstant [17]\n", "  11: IntConstant\n" },
-    { "  13: IntConstant [17]\n", "  13: IntConstant\n" },
-    { "  9: Add(3, 5) [21]\n",    "  28: IntConstant\n" },
-    { "  17: Add(11, 13) [21]\n", "  29: IntConstant\n" },
-    { "  21: Add(9, 17) [24]\n",  "  30: IntConstant [24]\n" },
-    { "  24: Return(21)\n",       "  24: Return(30)\n" }
-  };
-  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
-
-  // Expected difference after dead code elimination.
-  diff_t expected_dce_diff = {
-    { "  3: IntConstant\n",  removed },
-    { "  5: IntConstant\n",  removed },
-    { "  11: IntConstant\n", removed },
-    { "  13: IntConstant\n", removed },
-    { "  28: IntConstant\n", removed },
-    { "  29: IntConstant\n", removed }
-  };
-  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
-
-  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
-}
-
-/**
- * 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(ConstantPropagation, IntConstantFoldingOnSubtraction) {
-  const 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"
-    "  3: IntConstant [9]\n"
-    "  5: IntConstant [9]\n"
-    "  14: SuspendCheck\n"
-    "  15: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  9: Sub(3, 5) [12]\n"
-    "  12: Return(9)\n"
-    "BasicBlock 2, pred: 1\n"
-    "  13: Exit\n";
-
-  // Expected difference after constant propagation.
-  diff_t expected_cp_diff = {
-    { "  3: IntConstant [9]\n", "  3: IntConstant\n" },
-    { "  5: IntConstant [9]\n", "  5: IntConstant\n" },
-    { "  9: Sub(3, 5) [12]\n",  "  16: IntConstant [12]\n" },
-    { "  12: Return(9)\n",      "  12: Return(16)\n" }
-  };
-  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
-
-  // Expected difference after dead code elimination.
-  diff_t expected_dce_diff = {
-    { "  3: IntConstant\n", removed },
-    { "  5: IntConstant\n", removed }
-  };
-  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
-
-  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
-}
-
-#define SIX_REGISTERS_CODE_ITEM(...)                                     \
-    { 6, 0, 0, 0, 0, 0, NUM_INSTRUCTIONS(__VA_ARGS__), 0, __VA_ARGS__ }
-
-/**
- * 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(ConstantPropagation, LongConstantFoldingOnAddition) {
-  const 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"
-    "  6: LongConstant [12]\n"
-    "  8: LongConstant [12]\n"
-    "  17: SuspendCheck\n"
-    "  18: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  12: Add(6, 8) [15]\n"
-    "  15: Return(12)\n"
-    "BasicBlock 2, pred: 1\n"
-    "  16: Exit\n";
-
-  // Expected difference after constant propagation.
-  diff_t expected_cp_diff = {
-    { "  6: LongConstant [12]\n", "  6: LongConstant\n" },
-    { "  8: LongConstant [12]\n", "  8: LongConstant\n" },
-    { "  12: Add(6, 8) [15]\n",   "  19: LongConstant [15]\n" },
-    { "  15: Return(12)\n",       "  15: Return(19)\n" }
-  };
-  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
-
-  // Expected difference after dead code elimination.
-  diff_t expected_dce_diff = {
-    { "  6: LongConstant\n", removed },
-    { "  8: LongConstant\n", removed }
-  };
-  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
-
-  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
-}
-
-/**
- * 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(ConstantPropagation, LongConstantFoldingOnSubtraction) {
-  const 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"
-    "  6: LongConstant [12]\n"
-    "  8: LongConstant [12]\n"
-    "  17: SuspendCheck\n"
-    "  18: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 2\n"
-    "  12: Sub(6, 8) [15]\n"
-    "  15: Return(12)\n"
-    "BasicBlock 2, pred: 1\n"
-    "  16: Exit\n";
-
-  // Expected difference after constant propagation.
-  diff_t expected_cp_diff = {
-    { "  6: LongConstant [12]\n", "  6: LongConstant\n" },
-    { "  8: LongConstant [12]\n", "  8: LongConstant\n" },
-    { "  12: Sub(6, 8) [15]\n",   "  19: LongConstant [15]\n" },
-    { "  15: Return(12)\n",       "  15: Return(19)\n" }
-  };
-  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
-
-  // Expected difference after dead code elimination.
-  diff_t expected_dce_diff = {
-    { "  6: LongConstant\n", removed },
-    { "  8: LongConstant\n", removed }
-  };
-  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
-
-  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
-}
-
-/**
- * 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 the dominator tree.
- *
- *                              16-bit
- *                              offset
- *                              ------
- *     v0 <- 0                   0.     const/4 v0, #+0
- *     v1 <- 1                   1.     const/4 v1, #+1
- *     v2 <- v0 + v1             2.     add-int v2, v0, v1
- *     goto L2                   4.     goto +4
- * L1: v1 <- v0 + 3              5.     add-int/lit16 v1, v0, #+3
- *     goto L3                   7.     goto +4
- * L2: v0 <- v2 + 2              8.     add-int/lit16 v0, v2, #+2
- *     goto L1                  10.     goto +(-5)
- * L3: v2 <- v1 + 4             11.     add-int/lit16 v2, v1, #+4
- *     return v2                13.     return v2
- */
-TEST(ConstantPropagation, IntConstantFoldingAndJumps) {
-  const uint16_t data[] = THREE_REGISTERS_CODE_ITEM(
-    Instruction::CONST_4 | 0 << 8 | 0 << 12,
-    Instruction::CONST_4 | 1 << 8 | 1 << 12,
-    Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
-    Instruction::GOTO | 4 << 8,
-    Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 3,
-    Instruction::GOTO | 4 << 8,
-    Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 2,
-    static_cast<uint16_t>(Instruction::GOTO | -5 << 8),
-    Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4,
-    Instruction::RETURN | 2 << 8);
-
-  std::string expected_before =
-    "BasicBlock 0, succ: 1\n"
-    "  3: IntConstant [9]\n"
-    "  5: IntConstant [9]\n"
-    "  13: IntConstant [14]\n"
-    "  18: IntConstant [19]\n"
-    "  24: IntConstant [25]\n"
-    "  30: SuspendCheck\n"
-    "  31: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 3\n"
-    "  9: Add(3, 5) [19]\n"
-    "  11: Goto 3\n"
-    "BasicBlock 2, pred: 3, succ: 4\n"
-    "  14: Add(19, 13) [25]\n"
-    "  16: Goto 4\n"
-    "BasicBlock 3, pred: 1, succ: 2\n"
-    "  19: Add(9, 18) [14]\n"
-    "  21: SuspendCheck\n"
-    "  22: Goto 2\n"
-    "BasicBlock 4, pred: 2, succ: 5\n"
-    "  25: Add(14, 24) [28]\n"
-    "  28: Return(25)\n"
-    "BasicBlock 5, pred: 4\n"
-    "  29: Exit\n";
-
-  // Expected difference after constant propagation.
-  diff_t expected_cp_diff = {
-    { "  3: IntConstant [9]\n",   "  3: IntConstant\n" },
-    { "  5: IntConstant [9]\n",   "  5: IntConstant []\n" },
-    { "  13: IntConstant [14]\n", "  13: IntConstant\n" },
-    { "  18: IntConstant [19]\n", "  18: IntConstant\n" },
-    { "  24: IntConstant [25]\n", "  24: IntConstant\n" },
-    { "  9: Add(3, 5) [19]\n",    "  32: IntConstant []\n" },
-    { "  14: Add(19, 13) [25]\n", "  34: IntConstant\n" },
-    { "  19: Add(9, 18) [14]\n",  "  33: IntConstant []\n" },
-    { "  25: Add(14, 24) [28]\n", "  35: IntConstant [28]\n" },
-    { "  28: Return(25)\n",       "  28: Return(35)\n"}
-  };
-  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
-
-  // Expected difference after dead code elimination.
-  diff_t expected_dce_diff = {
-    { "  3: IntConstant\n",     removed },
-    { "  13: IntConstant\n",    removed },
-    { "  18: IntConstant\n",    removed },
-    { "  24: IntConstant\n",    removed },
-    { "  34: IntConstant\n",    removed },
-  };
-  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
-
-  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
-}
-
-
-/**
- * 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(ConstantPropagation, ConstantCondition) {
-  const 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 [15, 22, 8]\n"
-    "  5: IntConstant [22, 8]\n"
-    "  19: SuspendCheck\n"
-    "  20: Goto 1\n"
-    "BasicBlock 1, pred: 0, succ: 5, 2\n"
-    "  8: GreaterThanOrEqual(3, 5) [9]\n"
-    "  9: If(8)\n"
-    "BasicBlock 2, pred: 1, succ: 3\n"
-    "  12: Goto 3\n"
-    "BasicBlock 3, pred: 2, 5, succ: 4\n"
-    "  22: Phi(3, 5) [15]\n"
-    "  15: Add(22, 3)\n"
-    "  17: ReturnVoid\n"
-    "BasicBlock 4, pred: 3\n"
-    "  18: Exit\n"
-    "BasicBlock 5, pred: 1, succ: 3\n"
-    "  21: Goto 3\n";
-
-  // Expected difference after constant propagation.
-  diff_t expected_cp_diff = {
-    { "  3: IntConstant [15, 22, 8]\n",      "  3: IntConstant [15, 22]\n" },
-    { "  5: IntConstant [22, 8]\n",          "  5: IntConstant [22]\n" },
-    { "  8: GreaterThanOrEqual(3, 5) [9]\n", "  23: IntConstant [9]\n" },
-    { "  9: If(8)\n",                        "  9: If(23)\n" }
-  };
-  std::string expected_after_cp = Patch(expected_before, expected_cp_diff);
-
-  // Expected difference after dead code elimination.
-  diff_t expected_dce_diff = {
-    { "  3: IntConstant [15, 22]\n", "  3: IntConstant [22]\n" },
-    { "  22: Phi(3, 5) [15]\n",      "  22: Phi(3, 5)\n" },
-    { "  15: Add(22, 3)\n",          removed }
-  };
-  std::string expected_after_dce = Patch(expected_after_cp, expected_dce_diff);
-
-  TestCode(data, expected_before, expected_after_cp, expected_after_dce);
-}
-
-}  // namespace art