Home | History | Annotate | Download | only in optimizing
      1 /*
      2  * Copyright (C) 2014 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #include "dead_code_elimination.h"
     18 
     19 #include "arch/x86/instruction_set_features_x86.h"
     20 #include "code_generator_x86.h"
     21 #include "driver/compiler_options.h"
     22 #include "graph_checker.h"
     23 #include "optimizing_unit_test.h"
     24 #include "pretty_printer.h"
     25 
     26 #include "gtest/gtest.h"
     27 
     28 namespace art {
     29 
     30 class DeadCodeEliminationTest : public OptimizingUnitTest {
     31  protected:
     32   void TestCode(const std::vector<uint16_t>& data,
     33                 const std::string& expected_before,
     34                 const std::string& expected_after);
     35 };
     36 
     37 void DeadCodeEliminationTest::TestCode(const std::vector<uint16_t>& data,
     38                                        const std::string& expected_before,
     39                                        const std::string& expected_after) {
     40   HGraph* graph = CreateCFG(data);
     41   ASSERT_NE(graph, nullptr);
     42 
     43   StringPrettyPrinter printer_before(graph);
     44   printer_before.VisitInsertionOrder();
     45   std::string actual_before = printer_before.str();
     46   ASSERT_EQ(actual_before, expected_before);
     47 
     48   std::unique_ptr<const X86InstructionSetFeatures> features_x86(
     49       X86InstructionSetFeatures::FromCppDefines());
     50   x86::CodeGeneratorX86 codegenX86(graph, *features_x86.get(), CompilerOptions());
     51   HDeadCodeElimination(graph, nullptr /* stats */, "dead_code_elimination").Run();
     52   GraphChecker graph_checker(graph);
     53   graph_checker.Run();
     54   ASSERT_TRUE(graph_checker.IsValid());
     55 
     56   StringPrettyPrinter printer_after(graph);
     57   printer_after.VisitInsertionOrder();
     58   std::string actual_after = printer_after.str();
     59   ASSERT_EQ(actual_after, expected_after);
     60 }
     61 
     62 /**
     63  * Small three-register program.
     64  *
     65  *                              16-bit
     66  *                              offset
     67  *                              ------
     68  *     v1 <- 1                  0.      const/4 v1, #+1
     69  *     v0 <- 0                  1.      const/4 v0, #+0
     70  *     if v1 >= 0 goto L1       2.      if-gez v1, +3
     71  *     v0 <- v1                 4.      move v0, v1
     72  * L1: v2 <- v0 + v1            5.      add-int v2, v0, v1
     73  *     return-void              7.      return
     74  */
     75 TEST_F(DeadCodeEliminationTest, AdditionAndConditionalJump) {
     76   const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
     77     Instruction::CONST_4 | 1 << 8 | 1 << 12,
     78     Instruction::CONST_4 | 0 << 8 | 0 << 12,
     79     Instruction::IF_GEZ | 1 << 8, 3,
     80     Instruction::MOVE | 0 << 8 | 1 << 12,
     81     Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
     82     Instruction::RETURN_VOID);
     83 
     84   std::string expected_before =
     85       "BasicBlock 0, succ: 1\n"
     86       "  3: IntConstant [9, 8, 5]\n"
     87       "  4: IntConstant [8, 5]\n"
     88       "  1: SuspendCheck\n"
     89       "  2: Goto 1\n"
     90       "BasicBlock 1, pred: 0, succ: 5, 2\n"
     91       "  5: GreaterThanOrEqual(3, 4) [6]\n"
     92       "  6: If(5)\n"
     93       "BasicBlock 2, pred: 1, succ: 3\n"
     94       "  7: Goto 3\n"
     95       "BasicBlock 3, pred: 5, 2, succ: 4\n"
     96       "  8: Phi(4, 3) [9]\n"
     97       "  9: Add(8, 3)\n"
     98       "  10: ReturnVoid\n"
     99       "BasicBlock 4, pred: 3\n"
    100       "  11: Exit\n"
    101       "BasicBlock 5, pred: 1, succ: 3\n"
    102       "  0: Goto 3\n";
    103 
    104   // Expected difference after dead code elimination.
    105   diff_t expected_diff = {
    106     { "  3: IntConstant [9, 8, 5]\n",  "  3: IntConstant [8, 5]\n" },
    107     { "  8: Phi(4, 3) [9]\n",          "  8: Phi(4, 3)\n" },
    108     { "  9: Add(8, 3)\n",              removed }
    109   };
    110   std::string expected_after = Patch(expected_before, expected_diff);
    111 
    112   TestCode(data, expected_before, expected_after);
    113 }
    114 
    115 /**
    116  * Three-register program with jumps leading to the creation of many
    117  * blocks.
    118  *
    119  * The intent of this test is to ensure that all dead instructions are
    120  * actually pruned at compile-time, thanks to the (backward)
    121  * post-order traversal of the the dominator tree.
    122  *
    123  *                              16-bit
    124  *                              offset
    125  *                              ------
    126  *     v0 <- 0                   0.     const/4 v0, #+0
    127  *     v1 <- 1                   1.     const/4 v1, #+1
    128  *     v2 <- v0 + v1             2.     add-int v2, v0, v1
    129  *     goto L2                   4.     goto +4
    130  * L1: v1 <- v0 + 3              5.     add-int/lit16 v1, v0, #+3
    131  *     goto L3                   7.     goto +4
    132  * L2: v0 <- v2 + 2              8.     add-int/lit16 v0, v2, #+2
    133  *     goto L1                  10.     goto +(-5)
    134  * L3: v2 <- v1 + 4             11.     add-int/lit16 v2, v1, #+4
    135  *     return                   13.     return-void
    136  */
    137 TEST_F(DeadCodeEliminationTest, AdditionsAndInconditionalJumps) {
    138   const std::vector<uint16_t> data = THREE_REGISTERS_CODE_ITEM(
    139     Instruction::CONST_4 | 0 << 8 | 0 << 12,
    140     Instruction::CONST_4 | 1 << 8 | 1 << 12,
    141     Instruction::ADD_INT | 2 << 8, 0 | 1 << 8,
    142     Instruction::GOTO | 4 << 8,
    143     Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 3,
    144     Instruction::GOTO | 4 << 8,
    145     Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 2,
    146     static_cast<uint16_t>(Instruction::GOTO | 0xFFFFFFFB << 8),
    147     Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4,
    148     Instruction::RETURN_VOID);
    149 
    150   std::string expected_before =
    151       "BasicBlock 0, succ: 1\n"
    152       "  2: IntConstant [4]\n"
    153       "  3: IntConstant [4]\n"
    154       "  6: IntConstant [7]\n"
    155       "  9: IntConstant [10]\n"
    156       "  12: IntConstant [13]\n"
    157       "  0: SuspendCheck\n"
    158       "  1: Goto 1\n"
    159       "BasicBlock 1, pred: 0, succ: 3\n"
    160       "  4: Add(2, 3) [7]\n"
    161       "  5: Goto 3\n"
    162       "BasicBlock 2, pred: 3, succ: 4\n"
    163       "  10: Add(7, 9) [13]\n"
    164       "  11: Goto 4\n"
    165       "BasicBlock 3, pred: 1, succ: 2\n"
    166       "  7: Add(4, 6) [10]\n"
    167       "  8: Goto 2\n"
    168       "BasicBlock 4, pred: 2, succ: 5\n"
    169       "  13: Add(10, 12)\n"
    170       "  14: ReturnVoid\n"
    171       "BasicBlock 5, pred: 4\n"
    172       "  15: Exit\n";
    173 
    174   std::string expected_after =
    175       "BasicBlock 0, succ: 1\n"
    176       "  0: SuspendCheck\n"
    177       "  1: Goto 1\n"
    178       "BasicBlock 1, pred: 0, succ: 5\n"
    179       "  14: ReturnVoid\n"
    180       "BasicBlock 5, pred: 1\n"
    181       "  15: Exit\n";
    182 
    183   TestCode(data, expected_before, expected_after);
    184 }
    185 
    186 }  // namespace art
    187