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 "base/arena_allocator.h" 18 #include "builder.h" 19 #include "gvn.h" 20 #include "nodes.h" 21 #include "optimizing_unit_test.h" 22 #include "side_effects_analysis.h" 23 24 #include "gtest/gtest.h" 25 26 namespace art { 27 28 TEST(GVNTest, LocalFieldElimination) { 29 ArenaPool pool; 30 ArenaAllocator allocator(&pool); 31 32 HGraph* graph = CreateGraph(&allocator); 33 HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 34 graph->AddBlock(entry); 35 graph->SetEntryBlock(entry); 36 HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot); 37 entry->AddInstruction(parameter); 38 39 HBasicBlock* block = new (&allocator) HBasicBlock(graph); 40 graph->AddBlock(block); 41 entry->AddSuccessor(block); 42 43 block->AddInstruction( 44 new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, 45 MemberOffset(42), false)); 46 block->AddInstruction( 47 new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, 48 MemberOffset(42), false)); 49 HInstruction* to_remove = block->GetLastInstruction(); 50 block->AddInstruction( 51 new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, 52 MemberOffset(43), false)); 53 HInstruction* different_offset = block->GetLastInstruction(); 54 // Kill the value. 55 block->AddInstruction(new (&allocator) HInstanceFieldSet( 56 parameter, parameter, Primitive::kPrimNot, MemberOffset(42), false)); 57 block->AddInstruction( 58 new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimNot, 59 MemberOffset(42), false)); 60 HInstruction* use_after_kill = block->GetLastInstruction(); 61 block->AddInstruction(new (&allocator) HExit()); 62 63 ASSERT_EQ(to_remove->GetBlock(), block); 64 ASSERT_EQ(different_offset->GetBlock(), block); 65 ASSERT_EQ(use_after_kill->GetBlock(), block); 66 67 graph->TryBuildingSsa(); 68 SideEffectsAnalysis side_effects(graph); 69 side_effects.Run(); 70 GVNOptimization(graph, side_effects).Run(); 71 72 ASSERT_TRUE(to_remove->GetBlock() == nullptr); 73 ASSERT_EQ(different_offset->GetBlock(), block); 74 ASSERT_EQ(use_after_kill->GetBlock(), block); 75 } 76 77 TEST(GVNTest, GlobalFieldElimination) { 78 ArenaPool pool; 79 ArenaAllocator allocator(&pool); 80 81 HGraph* graph = CreateGraph(&allocator); 82 HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 83 graph->AddBlock(entry); 84 graph->SetEntryBlock(entry); 85 HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot); 86 entry->AddInstruction(parameter); 87 88 HBasicBlock* block = new (&allocator) HBasicBlock(graph); 89 graph->AddBlock(block); 90 entry->AddSuccessor(block); 91 block->AddInstruction( 92 new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, 93 MemberOffset(42), false)); 94 95 block->AddInstruction(new (&allocator) HIf(block->GetLastInstruction())); 96 HBasicBlock* then = new (&allocator) HBasicBlock(graph); 97 HBasicBlock* else_ = new (&allocator) HBasicBlock(graph); 98 HBasicBlock* join = new (&allocator) HBasicBlock(graph); 99 graph->AddBlock(then); 100 graph->AddBlock(else_); 101 graph->AddBlock(join); 102 103 block->AddSuccessor(then); 104 block->AddSuccessor(else_); 105 then->AddSuccessor(join); 106 else_->AddSuccessor(join); 107 108 then->AddInstruction( 109 new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, 110 MemberOffset(42), false)); 111 then->AddInstruction(new (&allocator) HGoto()); 112 else_->AddInstruction( 113 new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, 114 MemberOffset(42), false)); 115 else_->AddInstruction(new (&allocator) HGoto()); 116 join->AddInstruction( 117 new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, 118 MemberOffset(42), false)); 119 join->AddInstruction(new (&allocator) HExit()); 120 121 graph->TryBuildingSsa(); 122 SideEffectsAnalysis side_effects(graph); 123 side_effects.Run(); 124 GVNOptimization(graph, side_effects).Run(); 125 126 // Check that all field get instructions have been GVN'ed. 127 ASSERT_TRUE(then->GetFirstInstruction()->IsGoto()); 128 ASSERT_TRUE(else_->GetFirstInstruction()->IsGoto()); 129 ASSERT_TRUE(join->GetFirstInstruction()->IsExit()); 130 } 131 132 TEST(GVNTest, LoopFieldElimination) { 133 ArenaPool pool; 134 ArenaAllocator allocator(&pool); 135 136 HGraph* graph = CreateGraph(&allocator); 137 HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 138 graph->AddBlock(entry); 139 graph->SetEntryBlock(entry); 140 141 HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimNot); 142 entry->AddInstruction(parameter); 143 144 HBasicBlock* block = new (&allocator) HBasicBlock(graph); 145 graph->AddBlock(block); 146 entry->AddSuccessor(block); 147 block->AddInstruction( 148 new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, 149 MemberOffset(42), false)); 150 block->AddInstruction(new (&allocator) HGoto()); 151 152 HBasicBlock* loop_header = new (&allocator) HBasicBlock(graph); 153 HBasicBlock* loop_body = new (&allocator) HBasicBlock(graph); 154 HBasicBlock* exit = new (&allocator) HBasicBlock(graph); 155 156 graph->AddBlock(loop_header); 157 graph->AddBlock(loop_body); 158 graph->AddBlock(exit); 159 block->AddSuccessor(loop_header); 160 loop_header->AddSuccessor(loop_body); 161 loop_header->AddSuccessor(exit); 162 loop_body->AddSuccessor(loop_header); 163 164 loop_header->AddInstruction( 165 new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, 166 MemberOffset(42), false)); 167 HInstruction* field_get_in_loop_header = loop_header->GetLastInstruction(); 168 loop_header->AddInstruction(new (&allocator) HIf(block->GetLastInstruction())); 169 170 // Kill inside the loop body to prevent field gets inside the loop header 171 // and the body to be GVN'ed. 172 loop_body->AddInstruction(new (&allocator) HInstanceFieldSet( 173 parameter, parameter, Primitive::kPrimNot, MemberOffset(42), false)); 174 HInstruction* field_set = loop_body->GetLastInstruction(); 175 loop_body->AddInstruction( 176 new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, 177 MemberOffset(42), false)); 178 HInstruction* field_get_in_loop_body = loop_body->GetLastInstruction(); 179 loop_body->AddInstruction(new (&allocator) HGoto()); 180 181 exit->AddInstruction( 182 new (&allocator) HInstanceFieldGet(parameter, Primitive::kPrimBoolean, 183 MemberOffset(42), false)); 184 HInstruction* field_get_in_exit = exit->GetLastInstruction(); 185 exit->AddInstruction(new (&allocator) HExit()); 186 187 ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header); 188 ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body); 189 ASSERT_EQ(field_get_in_exit->GetBlock(), exit); 190 191 graph->TryBuildingSsa(); 192 { 193 SideEffectsAnalysis side_effects(graph); 194 side_effects.Run(); 195 GVNOptimization(graph, side_effects).Run(); 196 } 197 198 // Check that all field get instructions are still there. 199 ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header); 200 ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body); 201 // The exit block is dominated by the loop header, whose field get 202 // does not get killed by the loop flags. 203 ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr); 204 205 // Now remove the field set, and check that all field get instructions have been GVN'ed. 206 loop_body->RemoveInstruction(field_set); 207 { 208 SideEffectsAnalysis side_effects(graph); 209 side_effects.Run(); 210 GVNOptimization(graph, side_effects).Run(); 211 } 212 213 ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr); 214 ASSERT_TRUE(field_get_in_loop_body->GetBlock() == nullptr); 215 ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr); 216 } 217 218 // Test that inner loops affect the side effects of the outer loop. 219 TEST(GVNTest, LoopSideEffects) { 220 ArenaPool pool; 221 ArenaAllocator allocator(&pool); 222 223 HGraph* graph = CreateGraph(&allocator); 224 HBasicBlock* entry = new (&allocator) HBasicBlock(graph); 225 graph->AddBlock(entry); 226 graph->SetEntryBlock(entry); 227 228 HBasicBlock* outer_loop_header = new (&allocator) HBasicBlock(graph); 229 HBasicBlock* outer_loop_body = new (&allocator) HBasicBlock(graph); 230 HBasicBlock* outer_loop_exit = new (&allocator) HBasicBlock(graph); 231 HBasicBlock* inner_loop_header = new (&allocator) HBasicBlock(graph); 232 HBasicBlock* inner_loop_body = new (&allocator) HBasicBlock(graph); 233 HBasicBlock* inner_loop_exit = new (&allocator) HBasicBlock(graph); 234 235 graph->AddBlock(outer_loop_header); 236 graph->AddBlock(outer_loop_body); 237 graph->AddBlock(outer_loop_exit); 238 graph->AddBlock(inner_loop_header); 239 graph->AddBlock(inner_loop_body); 240 graph->AddBlock(inner_loop_exit); 241 242 entry->AddSuccessor(outer_loop_header); 243 outer_loop_header->AddSuccessor(outer_loop_body); 244 outer_loop_header->AddSuccessor(outer_loop_exit); 245 outer_loop_body->AddSuccessor(inner_loop_header); 246 inner_loop_header->AddSuccessor(inner_loop_body); 247 inner_loop_header->AddSuccessor(inner_loop_exit); 248 inner_loop_body->AddSuccessor(inner_loop_header); 249 inner_loop_exit->AddSuccessor(outer_loop_header); 250 251 HInstruction* parameter = new (&allocator) HParameterValue(0, Primitive::kPrimBoolean); 252 entry->AddInstruction(parameter); 253 entry->AddInstruction(new (&allocator) HGoto()); 254 outer_loop_header->AddInstruction(new (&allocator) HIf(parameter)); 255 outer_loop_body->AddInstruction(new (&allocator) HGoto()); 256 inner_loop_header->AddInstruction(new (&allocator) HIf(parameter)); 257 inner_loop_body->AddInstruction(new (&allocator) HGoto()); 258 inner_loop_exit->AddInstruction(new (&allocator) HGoto()); 259 outer_loop_exit->AddInstruction(new (&allocator) HExit()); 260 261 graph->TryBuildingSsa(); 262 263 ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn( 264 *outer_loop_header->GetLoopInformation())); 265 266 // Check that the loops don't have side effects. 267 { 268 // Make one block with a side effect. 269 entry->AddInstruction(new (&allocator) HInstanceFieldSet( 270 parameter, parameter, Primitive::kPrimNot, MemberOffset(42), false)); 271 272 SideEffectsAnalysis side_effects(graph); 273 side_effects.Run(); 274 275 ASSERT_TRUE(side_effects.GetBlockEffects(entry).HasSideEffects()); 276 ASSERT_FALSE(side_effects.GetLoopEffects(outer_loop_header).HasSideEffects()); 277 ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).HasSideEffects()); 278 } 279 280 // Check that the side effects of the outer loop does not affect the inner loop. 281 { 282 outer_loop_body->InsertInstructionBefore( 283 new (&allocator) HInstanceFieldSet( 284 parameter, parameter, Primitive::kPrimNot, MemberOffset(42), false), 285 outer_loop_body->GetLastInstruction()); 286 287 SideEffectsAnalysis side_effects(graph); 288 side_effects.Run(); 289 290 ASSERT_TRUE(side_effects.GetBlockEffects(entry).HasSideEffects()); 291 ASSERT_TRUE(side_effects.GetBlockEffects(outer_loop_body).HasSideEffects()); 292 ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).HasSideEffects()); 293 ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).HasSideEffects()); 294 } 295 296 // Check that the side effects of the inner loop affects the outer loop. 297 { 298 outer_loop_body->RemoveInstruction(outer_loop_body->GetFirstInstruction()); 299 inner_loop_body->InsertInstructionBefore( 300 new (&allocator) HInstanceFieldSet( 301 parameter, parameter, Primitive::kPrimNot, MemberOffset(42), false), 302 inner_loop_body->GetLastInstruction()); 303 304 SideEffectsAnalysis side_effects(graph); 305 side_effects.Run(); 306 307 ASSERT_TRUE(side_effects.GetBlockEffects(entry).HasSideEffects()); 308 ASSERT_FALSE(side_effects.GetBlockEffects(outer_loop_body).HasSideEffects()); 309 ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).HasSideEffects()); 310 ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).HasSideEffects()); 311 } 312 } 313 } // namespace art 314
