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 <fstream> 18 19 #include "base/stringprintf.h" 20 #include "builder.h" 21 #include "code_generator.h" 22 #include "dex_file.h" 23 #include "dex_instruction.h" 24 #include "graph_visualizer.h" 25 #include "nodes.h" 26 #include "optimizing_unit_test.h" 27 #include "pretty_printer.h" 28 #include "ssa_builder.h" 29 #include "ssa_liveness_analysis.h" 30 #include "utils/arena_allocator.h" 31 32 #include "gtest/gtest.h" 33 34 namespace art { 35 36 static void TestCode(const uint16_t* data, const int* expected_order, size_t number_of_blocks) { 37 ArenaPool pool; 38 ArenaAllocator allocator(&pool); 39 HGraphBuilder builder(&allocator); 40 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); 41 HGraph* graph = builder.BuildGraph(*item); 42 ASSERT_NE(graph, nullptr); 43 44 graph->BuildDominatorTree(); 45 graph->TransformToSSA(); 46 graph->FindNaturalLoops(); 47 48 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86); 49 SsaLivenessAnalysis liveness(*graph, codegen); 50 liveness.Analyze(); 51 52 ASSERT_EQ(liveness.GetLinearPostOrder().Size(), number_of_blocks); 53 for (size_t i = 0; i < number_of_blocks; ++i) { 54 ASSERT_EQ(liveness.GetLinearPostOrder().Get(number_of_blocks - i - 1)->GetBlockId(), 55 expected_order[i]); 56 } 57 } 58 59 TEST(LinearizeTest, CFG1) { 60 // Structure of this graph (+ are back edges) 61 // Block0 62 // | 63 // Block1 64 // | 65 // Block2 ++++++ 66 // / \ + 67 // Block5 Block7 + 68 // | | + 69 // Block6 Block3 + 70 // + / \ + 71 // Block4 Block8 72 73 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 74 Instruction::CONST_4 | 0 | 0, 75 Instruction::IF_EQ, 5, 76 Instruction::IF_EQ, 0xFFFE, 77 Instruction::GOTO | 0xFE00, 78 Instruction::RETURN_VOID); 79 80 const int blocks[] = {0, 1, 2, 7, 3, 4, 8, 5, 6}; 81 TestCode(data, blocks, 9); 82 } 83 84 TEST(LinearizeTest, CFG2) { 85 // Structure of this graph (+ are back edges) 86 // Block0 87 // | 88 // Block1 89 // | 90 // Block2 ++++++ 91 // / \ + 92 // Block3 Block7 + 93 // | | + 94 // Block6 Block4 + 95 // + / \ + 96 // Block5 Block8 97 98 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 99 Instruction::CONST_4 | 0 | 0, 100 Instruction::IF_EQ, 3, 101 Instruction::RETURN_VOID, 102 Instruction::IF_EQ, 0xFFFD, 103 Instruction::GOTO | 0xFE00); 104 105 const int blocks[] = {0, 1, 2, 7, 4, 5, 8, 3, 6}; 106 TestCode(data, blocks, 9); 107 } 108 109 TEST(LinearizeTest, CFG3) { 110 // Structure of this graph (+ are back edges) 111 // Block0 112 // | 113 // Block1 114 // | 115 // Block2 ++++++ 116 // / \ + 117 // Block3 Block8 + 118 // | | + 119 // Block7 Block5 + 120 // / + \ + 121 // Block6 + Block9 122 // | + 123 // Block4 ++ 124 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 125 Instruction::CONST_4 | 0 | 0, 126 Instruction::IF_EQ, 4, 127 Instruction::RETURN_VOID, 128 Instruction::GOTO | 0x0100, 129 Instruction::IF_EQ, 0xFFFC, 130 Instruction::GOTO | 0xFD00); 131 132 const int blocks[] = {0, 1, 2, 8, 5, 6, 4, 9, 3, 7}; 133 TestCode(data, blocks, 10); 134 } 135 136 TEST(LinearizeTest, CFG4) { 137 /* Structure of this graph (+ are back edges) 138 // Block0 139 // | 140 // Block1 141 // | 142 // Block2 143 // / + \ 144 // Block6 + Block8 145 // | + | 146 // Block7 + Block3 +++++++ 147 // + / \ + 148 // Block9 Block10 + 149 // | + 150 // Block4 + 151 // + / \ + 152 // Block5 Block11 153 */ 154 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 155 Instruction::CONST_4 | 0 | 0, 156 Instruction::IF_EQ, 7, 157 Instruction::IF_EQ, 0xFFFE, 158 Instruction::IF_EQ, 0xFFFE, 159 Instruction::GOTO | 0xFE00, 160 Instruction::RETURN_VOID); 161 162 const int blocks[] = {0, 1, 2, 8, 3, 10, 4, 5, 11, 9, 6, 7}; 163 TestCode(data, blocks, 12); 164 } 165 166 TEST(LinearizeTest, CFG5) { 167 /* Structure of this graph (+ are back edges) 168 // Block0 169 // | 170 // Block1 171 // | 172 // Block2 173 // / + \ 174 // Block3 + Block8 175 // | + | 176 // Block7 + Block4 +++++++ 177 // + / \ + 178 // Block9 Block10 + 179 // | + 180 // Block5 + 181 // +/ \ + 182 // Block6 Block11 183 */ 184 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 185 Instruction::CONST_4 | 0 | 0, 186 Instruction::IF_EQ, 3, 187 Instruction::RETURN_VOID, 188 Instruction::IF_EQ, 0xFFFD, 189 Instruction::IF_EQ, 0xFFFE, 190 Instruction::GOTO | 0xFE00); 191 192 const int blocks[] = {0, 1, 2, 8, 4, 10, 5, 6, 11, 9, 3, 7}; 193 TestCode(data, blocks, 12); 194 } 195 196 } // namespace art 197
