172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain/* 272bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * Copyright (C) 2014 The Android Open Source Project 372bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * 472bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * Licensed under the Apache License, Version 2.0 (the "License"); 572bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * you may not use this file except in compliance with the License. 672bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * You may obtain a copy of the License at 772bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * 872bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * http://www.apache.org/licenses/LICENSE-2.0 972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * 1072bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * Unless required by applicable law or agreed to in writing, software 1172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * distributed under the License is distributed on an "AS IS" BASIS, 1272bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1372bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * See the License for the specific language governing permissions and 1472bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * limitations under the License. 1572bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain */ 1672bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 17fb8d279bc011b31d0765dc7ca59afea324fd0d0cMark Mendell#include "arch/x86/instruction_set_features_x86.h" 1875be28332b278cff9039b54bfb228ac72f539cccRoland Levillain#include "code_generator_x86.h" 1972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain#include "dead_code_elimination.h" 20cd6dffedf1bd8e6dfb3fb0c933551f9a90f7de3fCalin Juravle#include "driver/compiler_options.h" 2172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain#include "graph_checker.h" 2272bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain#include "optimizing_unit_test.h" 2375be28332b278cff9039b54bfb228ac72f539cccRoland Levillain#include "pretty_printer.h" 2472bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 2572bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain#include "gtest/gtest.h" 2672bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 2772bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillainnamespace art { 2872bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 294833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdilclass DeadCodeEliminationTest : public CommonCompilerTest {}; 304833f5a1990c76bc2be89504225fb13cca22bedfDavid Brazdil 3172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillainstatic void TestCode(const uint16_t* data, 3272bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain const std::string& expected_before, 3372bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain const std::string& expected_after) { 3472bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain ArenaPool pool; 3572bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain ArenaAllocator allocator(&pool); 3672bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain HGraph* graph = CreateCFG(&allocator, data); 3772bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain ASSERT_NE(graph, nullptr); 3872bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 3972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain StringPrettyPrinter printer_before(graph); 4072bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain printer_before.VisitInsertionOrder(); 4172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain std::string actual_before = printer_before.str(); 4272bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain ASSERT_EQ(actual_before, expected_before); 4372bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 44fb8d279bc011b31d0765dc7ca59afea324fd0d0cMark Mendell std::unique_ptr<const X86InstructionSetFeatures> features_x86( 45fb8d279bc011b31d0765dc7ca59afea324fd0d0cMark Mendell X86InstructionSetFeatures::FromCppDefines()); 46fb8d279bc011b31d0765dc7ca59afea324fd0d0cMark Mendell x86::CodeGeneratorX86 codegenX86(graph, *features_x86.get(), CompilerOptions()); 47862aaefdd63d8058b54a7d956a0229eec9dcbde6Calin Juravle HDeadCodeElimination(graph).Run(); 48badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil GraphChecker graph_checker(graph); 49badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil graph_checker.Run(); 50badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil ASSERT_TRUE(graph_checker.IsValid()); 5172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 5272bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain StringPrettyPrinter printer_after(graph); 5372bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain printer_after.VisitInsertionOrder(); 5472bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain std::string actual_after = printer_after.str(); 5572bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain ASSERT_EQ(actual_after, expected_after); 5672bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain} 5772bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 5872bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain/** 5972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * Small three-register program. 6072bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * 6172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * 16-bit 6272bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * offset 6372bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * ------ 6472bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * v1 <- 1 0. const/4 v1, #+1 6572bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * v0 <- 0 1. const/4 v0, #+0 6672bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * if v1 >= 0 goto L1 2. if-gez v1, +3 6772bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * v0 <- v1 4. move v0, v1 6872bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * L1: v2 <- v0 + v1 5. add-int v2, v0, v1 6972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * return-void 7. return 7072bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain */ 714833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(DeadCodeEliminationTest, AdditionAndConditionalJump) { 7272bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( 7372bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::CONST_4 | 1 << 8 | 1 << 12, 7472bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::CONST_4 | 0 << 8 | 0 << 12, 7572bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::IF_GEZ | 1 << 8, 3, 7672bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::MOVE | 0 << 8 | 1 << 12, 7772bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::ADD_INT | 2 << 8, 0 | 1 << 8, 7872bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::RETURN_VOID); 7972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 8072bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain std::string expected_before = 8186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 0, succ: 1\n" 82dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 3: IntConstant [9, 8, 5]\n" 83dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 4: IntConstant [8, 5]\n" 84dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 1: SuspendCheck\n" 85dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 2: Goto 1\n" 8686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 1, pred: 0, succ: 5, 2\n" 87dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 5: GreaterThanOrEqual(3, 4) [6]\n" 88dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 6: If(5)\n" 8986ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 2, pred: 1, succ: 3\n" 90dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 7: Goto 3\n" 9186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 3, pred: 5, 2, succ: 4\n" 92dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 8: Phi(4, 3) [9]\n" 93dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 9: Add(8, 3)\n" 94dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 10: ReturnVoid\n" 9586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 4, pred: 3\n" 96dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 11: Exit\n" 9786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 5, pred: 1, succ: 3\n" 9886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil " 0: Goto 3\n"; 9972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 10075be28332b278cff9039b54bfb228ac72f539cccRoland Levillain // Expected difference after dead code elimination. 10172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain diff_t expected_diff = { 102dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil { " 3: IntConstant [9, 8, 5]\n", " 3: IntConstant [8, 5]\n" }, 103dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil { " 8: Phi(4, 3) [9]\n", " 8: Phi(4, 3)\n" }, 104dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil { " 9: Add(8, 3)\n", removed } 10572bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain }; 10672bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain std::string expected_after = Patch(expected_before, expected_diff); 10772bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 10872bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain TestCode(data, expected_before, expected_after); 10972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain} 11072bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 11172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain/** 11272bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * Three-register program with jumps leading to the creation of many 11372bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * blocks. 11472bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * 11572bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * The intent of this test is to ensure that all dead instructions are 11672bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * actually pruned at compile-time, thanks to the (backward) 11772bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * post-order traversal of the the dominator tree. 11872bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * 11972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * 16-bit 12072bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * offset 12172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * ------ 12272bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * v0 <- 0 0. const/4 v0, #+0 12372bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * v1 <- 1 1. const/4 v1, #+1 12472bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * v2 <- v0 + v1 2. add-int v2, v0, v1 12572bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * goto L2 4. goto +4 12672bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * L1: v1 <- v0 + 3 5. add-int/lit16 v1, v0, #+3 12772bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * goto L3 7. goto +4 12872bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * L2: v0 <- v2 + 2 8. add-int/lit16 v0, v2, #+2 12972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * goto L1 10. goto +(-5) 13072bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * L3: v2 <- v1 + 4 11. add-int/lit16 v2, v1, #+4 13172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain * return 13. return-void 13272bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain */ 1334833f5a1990c76bc2be89504225fb13cca22bedfDavid BrazdilTEST_F(DeadCodeEliminationTest, AdditionsAndInconditionalJumps) { 13472bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain const uint16_t data[] = THREE_REGISTERS_CODE_ITEM( 13572bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::CONST_4 | 0 << 8 | 0 << 12, 13672bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::CONST_4 | 1 << 8 | 1 << 12, 13772bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::ADD_INT | 2 << 8, 0 | 1 << 8, 13872bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::GOTO | 4 << 8, 13972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::ADD_INT_LIT16 | 1 << 8 | 0 << 12, 3, 14072bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::GOTO | 4 << 8, 14172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::ADD_INT_LIT16 | 0 << 8 | 2 << 12, 2, 14258554b7de4b437ddef7ff550e62c8ec0b16f9264Andreas Gampe static_cast<uint16_t>(Instruction::GOTO | 0xFFFFFFFB << 8), 14372bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::ADD_INT_LIT16 | 2 << 8 | 1 << 12, 4, 14472bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain Instruction::RETURN_VOID); 14572bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 14672bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain std::string expected_before = 14786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 0, succ: 1\n" 148dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 2: IntConstant [4]\n" 149dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 3: IntConstant [4]\n" 150dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 6: IntConstant [7]\n" 151dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 9: IntConstant [10]\n" 152dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 12: IntConstant [13]\n" 153dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 0: SuspendCheck\n" 154dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 1: Goto 1\n" 15586ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 1, pred: 0, succ: 3\n" 156dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 4: Add(2, 3) [7]\n" 157dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 5: Goto 3\n" 15886ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 2, pred: 3, succ: 4\n" 159dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 10: Add(7, 9) [13]\n" 160dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 11: Goto 4\n" 16186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 3, pred: 1, succ: 2\n" 162dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 7: Add(4, 6) [10]\n" 163dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 8: Goto 2\n" 16486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 4, pred: 2, succ: 5\n" 165dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 13: Add(10, 12)\n" 166dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 14: ReturnVoid\n" 16786ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 5, pred: 4\n" 168dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 15: Exit\n"; 16972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 1701c533c17baff841e383a539fdd3c0a65135181b0David Brazdil std::string expected_after = 17186ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 0, succ: 1\n" 172dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 0: SuspendCheck\n" 173dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 1: Goto 1\n" 17486ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 1, pred: 0, succ: 5\n" 175dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 14: ReturnVoid\n" 17686ea7eeabe30c98bbe1651a51d03cb89776724e7David Brazdil "BasicBlock 5, pred: 1\n" 177dee58d6bb6d567fcd0c4f39d8d690c3acaf0e432David Brazdil " 15: Exit\n"; 17872bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 17972bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain TestCode(data, expected_before, expected_after); 18072bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain} 18172bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain 18272bceff11a98cc1ecdb64a6fae16c521f99ec6a7Roland Levillain} // namespace art 183