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 "builder.h" 18 #include "code_generator.h" 19 #include "dex_file.h" 20 #include "dex_instruction.h" 21 #include "nodes.h" 22 #include "optimizing_unit_test.h" 23 #include "ssa_liveness_analysis.h" 24 #include "utils/arena_allocator.h" 25 26 #include "gtest/gtest.h" 27 28 namespace art { 29 30 static HGraph* BuildGraph(const uint16_t* data, ArenaAllocator* allocator) { 31 HGraphBuilder builder(allocator); 32 const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data); 33 HGraph* graph = builder.BuildGraph(*item); 34 graph->BuildDominatorTree(); 35 graph->TransformToSSA(); 36 graph->FindNaturalLoops(); 37 return graph; 38 } 39 40 TEST(LiveRangesTest, CFG1) { 41 /* 42 * Test the following snippet: 43 * return 0; 44 * 45 * Which becomes the following graph (numbered by lifetime position): 46 * 2: constant0 47 * 4: goto 48 * | 49 * 8: return 50 * | 51 * 12: exit 52 */ 53 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 54 Instruction::CONST_4 | 0 | 0, 55 Instruction::RETURN); 56 57 ArenaPool pool; 58 ArenaAllocator allocator(&pool); 59 HGraph* graph = BuildGraph(data, &allocator); 60 61 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86); 62 SsaLivenessAnalysis liveness(*graph, codegen); 63 liveness.Analyze(); 64 65 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval(); 66 LiveRange* range = interval->GetFirstRange(); 67 ASSERT_EQ(2u, range->GetStart()); 68 // Last use is the return instruction. 69 ASSERT_EQ(9u, range->GetEnd()); 70 HBasicBlock* block = graph->GetBlocks().Get(1); 71 ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr); 72 ASSERT_EQ(8u, block->GetLastInstruction()->GetLifetimePosition()); 73 ASSERT_TRUE(range->GetNext() == nullptr); 74 } 75 76 TEST(LiveRangesTest, CFG2) { 77 /* 78 * Test the following snippet: 79 * var a = 0; 80 * if (0 == 0) { 81 * } else { 82 * } 83 * return a; 84 * 85 * Which becomes the following graph (numbered by lifetime position): 86 * 2: constant0 87 * 4: goto 88 * | 89 * 8: equal 90 * 10: if 91 * / \ 92 * 14: goto 18: goto 93 * \ / 94 * 22: return 95 * | 96 * 26: exit 97 */ 98 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 99 Instruction::CONST_4 | 0 | 0, 100 Instruction::IF_EQ, 3, 101 Instruction::GOTO | 0x100, 102 Instruction::RETURN | 0 << 8); 103 104 ArenaPool pool; 105 ArenaAllocator allocator(&pool); 106 HGraph* graph = BuildGraph(data, &allocator); 107 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86); 108 SsaLivenessAnalysis liveness(*graph, codegen); 109 liveness.Analyze(); 110 111 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval(); 112 LiveRange* range = interval->GetFirstRange(); 113 ASSERT_EQ(2u, range->GetStart()); 114 // Last use is the return instruction. 115 ASSERT_EQ(23u, range->GetEnd()); 116 HBasicBlock* block = graph->GetBlocks().Get(3); 117 ASSERT_TRUE(block->GetLastInstruction()->AsReturn() != nullptr); 118 ASSERT_EQ(22u, block->GetLastInstruction()->GetLifetimePosition()); 119 ASSERT_TRUE(range->GetNext() == nullptr); 120 } 121 122 TEST(LiveRangesTest, CFG3) { 123 /* 124 * Test the following snippet: 125 * var a = 0; 126 * if (0 == 0) { 127 * } else { 128 * a = 4; 129 * } 130 * return a; 131 * 132 * Which becomes the following graph (numbered by lifetime position): 133 * 2: constant0 134 * 4: constant4 135 * 6: goto 136 * | 137 * 10: equal 138 * 12: if 139 * / \ 140 * 16: goto 20: goto 141 * \ / 142 * 22: phi 143 * 24: return 144 * | 145 * 38: exit 146 */ 147 const uint16_t data[] = ONE_REGISTER_CODE_ITEM( 148 Instruction::CONST_4 | 0 | 0, 149 Instruction::IF_EQ, 3, 150 Instruction::CONST_4 | 4 << 12 | 0, 151 Instruction::RETURN | 0 << 8); 152 153 ArenaPool pool; 154 ArenaAllocator allocator(&pool); 155 HGraph* graph = BuildGraph(data, &allocator); 156 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86); 157 SsaLivenessAnalysis liveness(*graph, codegen); 158 liveness.Analyze(); 159 160 // Test for the 4 constant. 161 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval(); 162 LiveRange* range = interval->GetFirstRange(); 163 ASSERT_EQ(4u, range->GetStart()); 164 // Last use is the phi at the return block so instruction is live until 165 // the end of the then block. 166 ASSERT_EQ(18u, range->GetEnd()); 167 ASSERT_TRUE(range->GetNext() == nullptr); 168 169 // Test for the 0 constant. 170 interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval(); 171 // The then branch is a hole for this constant, therefore its interval has 2 ranges. 172 // First range starts from the definition and ends at the if block. 173 range = interval->GetFirstRange(); 174 ASSERT_EQ(2u, range->GetStart()); 175 // 14 is the end of the if block. 176 ASSERT_EQ(14u, range->GetEnd()); 177 // Second range is the else block. 178 range = range->GetNext(); 179 ASSERT_EQ(18u, range->GetStart()); 180 // Last use is the phi at the return block. 181 ASSERT_EQ(22u, range->GetEnd()); 182 ASSERT_TRUE(range->GetNext() == nullptr); 183 184 // Test for the phi. 185 interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval(); 186 range = interval->GetFirstRange(); 187 ASSERT_EQ(22u, liveness.GetInstructionFromSsaIndex(2)->GetLifetimePosition()); 188 ASSERT_EQ(22u, range->GetStart()); 189 ASSERT_EQ(25u, range->GetEnd()); 190 ASSERT_TRUE(range->GetNext() == nullptr); 191 } 192 193 TEST(LiveRangesTest, Loop) { 194 /* 195 * Test the following snippet: 196 * var a = 0; 197 * while (a == a) { 198 * a = 4; 199 * } 200 * return 5; 201 * 202 * Which becomes the following graph (numbered by lifetime position): 203 * 2: constant0 204 * 4: constant4 205 * 6: constant5 206 * 8: goto 207 * | 208 * 12: goto 209 * | 210 * 14: phi 211 * 16: equal 212 * 18: if +++++ 213 * | \ + 214 * | 22: goto 215 * | 216 * 26: return 217 * | 218 * 30: exit 219 */ 220 221 const uint16_t data[] = TWO_REGISTERS_CODE_ITEM( 222 Instruction::CONST_4 | 0 | 0, 223 Instruction::IF_EQ, 4, 224 Instruction::CONST_4 | 4 << 12 | 0, 225 Instruction::GOTO | 0xFD00, 226 Instruction::CONST_4 | 5 << 12 | 1 << 8, 227 Instruction::RETURN | 1 << 8); 228 229 ArenaPool pool; 230 ArenaAllocator allocator(&pool); 231 HGraph* graph = BuildGraph(data, &allocator); 232 CodeGenerator* codegen = CodeGenerator::Create(&allocator, graph, InstructionSet::kX86); 233 SsaLivenessAnalysis liveness(*graph, codegen); 234 liveness.Analyze(); 235 236 // Test for the 0 constant. 237 LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval(); 238 LiveRange* range = interval->GetFirstRange(); 239 ASSERT_EQ(2u, range->GetStart()); 240 // Last use is the loop phi so instruction is live until 241 // the end of the pre loop header. 242 ASSERT_EQ(14u, range->GetEnd()); 243 ASSERT_TRUE(range->GetNext() == nullptr); 244 245 // Test for the 4 constant. 246 interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval(); 247 range = interval->GetFirstRange(); 248 // The instruction is live until the end of the loop. 249 ASSERT_EQ(4u, range->GetStart()); 250 ASSERT_EQ(24u, range->GetEnd()); 251 ASSERT_TRUE(range->GetNext() == nullptr); 252 253 // Test for the 5 constant. 254 interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval(); 255 range = interval->GetFirstRange(); 256 // The instruction is live until the return instruction after the loop. 257 ASSERT_EQ(6u, range->GetStart()); 258 ASSERT_EQ(27u, range->GetEnd()); 259 ASSERT_TRUE(range->GetNext() == nullptr); 260 261 // Test for the phi. 262 interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval(); 263 range = interval->GetFirstRange(); 264 // Instruction is consumed by the if. 265 ASSERT_EQ(14u, range->GetStart()); 266 ASSERT_EQ(17u, range->GetEnd()); 267 ASSERT_TRUE(range->GetNext() == nullptr); 268 } 269 270 } // namespace art 271
