1 /* 2 * Copyright (C) 2015 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 "licm.h" 18 19 #include "base/arena_allocator.h" 20 #include "builder.h" 21 #include "nodes.h" 22 #include "optimizing_unit_test.h" 23 #include "side_effects_analysis.h" 24 25 namespace art { 26 27 /** 28 * Fixture class for the LICM tests. 29 */ 30 class LICMTest : public OptimizingUnitTest { 31 public: 32 LICMTest() 33 : entry_(nullptr), 34 loop_preheader_(nullptr), 35 loop_header_(nullptr), 36 loop_body_(nullptr), 37 return_(nullptr), 38 exit_(nullptr), 39 parameter_(nullptr), 40 int_constant_(nullptr), 41 float_constant_(nullptr) { 42 graph_ = CreateGraph(); 43 } 44 45 ~LICMTest() { } 46 47 // Builds a singly-nested loop structure in CFG. Tests can further populate 48 // the basic blocks with instructions to set up interesting scenarios. 49 void BuildLoop() { 50 entry_ = new (GetAllocator()) HBasicBlock(graph_); 51 loop_preheader_ = new (GetAllocator()) HBasicBlock(graph_); 52 loop_header_ = new (GetAllocator()) HBasicBlock(graph_); 53 loop_body_ = new (GetAllocator()) HBasicBlock(graph_); 54 return_ = new (GetAllocator()) HBasicBlock(graph_); 55 exit_ = new (GetAllocator()) HBasicBlock(graph_); 56 57 graph_->AddBlock(entry_); 58 graph_->AddBlock(loop_preheader_); 59 graph_->AddBlock(loop_header_); 60 graph_->AddBlock(loop_body_); 61 graph_->AddBlock(return_); 62 graph_->AddBlock(exit_); 63 64 graph_->SetEntryBlock(entry_); 65 graph_->SetExitBlock(exit_); 66 67 // Set up loop flow in CFG. 68 entry_->AddSuccessor(loop_preheader_); 69 loop_preheader_->AddSuccessor(loop_header_); 70 loop_header_->AddSuccessor(loop_body_); 71 loop_header_->AddSuccessor(return_); 72 loop_body_->AddSuccessor(loop_header_); 73 return_->AddSuccessor(exit_); 74 75 // Provide boiler-plate instructions. 76 parameter_ = new (GetAllocator()) HParameterValue(graph_->GetDexFile(), 77 dex::TypeIndex(0), 78 0, 79 DataType::Type::kReference); 80 entry_->AddInstruction(parameter_); 81 int_constant_ = graph_->GetIntConstant(42); 82 float_constant_ = graph_->GetFloatConstant(42.0f); 83 loop_preheader_->AddInstruction(new (GetAllocator()) HGoto()); 84 loop_header_->AddInstruction(new (GetAllocator()) HIf(parameter_)); 85 loop_body_->AddInstruction(new (GetAllocator()) HGoto()); 86 return_->AddInstruction(new (GetAllocator()) HReturnVoid()); 87 exit_->AddInstruction(new (GetAllocator()) HExit()); 88 } 89 90 // Performs LICM optimizations (after proper set up). 91 void PerformLICM() { 92 graph_->BuildDominatorTree(); 93 SideEffectsAnalysis side_effects(graph_); 94 side_effects.Run(); 95 LICM(graph_, side_effects, nullptr).Run(); 96 } 97 98 // General building fields. 99 HGraph* graph_; 100 101 // Specific basic blocks. 102 HBasicBlock* entry_; 103 HBasicBlock* loop_preheader_; 104 HBasicBlock* loop_header_; 105 HBasicBlock* loop_body_; 106 HBasicBlock* return_; 107 HBasicBlock* exit_; 108 109 HInstruction* parameter_; // "this" 110 HInstruction* int_constant_; 111 HInstruction* float_constant_; 112 }; 113 114 // 115 // The actual LICM tests. 116 // 117 118 TEST_F(LICMTest, FieldHoisting) { 119 BuildLoop(); 120 121 // Populate the loop with instructions: set/get field with different types. 122 HInstruction* get_field = new (GetAllocator()) HInstanceFieldGet(parameter_, 123 nullptr, 124 DataType::Type::kInt64, 125 MemberOffset(10), 126 false, 127 kUnknownFieldIndex, 128 kUnknownClassDefIndex, 129 graph_->GetDexFile(), 130 0); 131 loop_body_->InsertInstructionBefore(get_field, loop_body_->GetLastInstruction()); 132 HInstruction* set_field = new (GetAllocator()) HInstanceFieldSet( 133 parameter_, int_constant_, nullptr, DataType::Type::kInt32, MemberOffset(20), 134 false, kUnknownFieldIndex, kUnknownClassDefIndex, graph_->GetDexFile(), 0); 135 loop_body_->InsertInstructionBefore(set_field, loop_body_->GetLastInstruction()); 136 137 EXPECT_EQ(get_field->GetBlock(), loop_body_); 138 EXPECT_EQ(set_field->GetBlock(), loop_body_); 139 PerformLICM(); 140 EXPECT_EQ(get_field->GetBlock(), loop_preheader_); 141 EXPECT_EQ(set_field->GetBlock(), loop_body_); 142 } 143 144 TEST_F(LICMTest, NoFieldHoisting) { 145 BuildLoop(); 146 147 // Populate the loop with instructions: set/get field with same types. 148 ScopedNullHandle<mirror::DexCache> dex_cache; 149 HInstruction* get_field = new (GetAllocator()) HInstanceFieldGet(parameter_, 150 nullptr, 151 DataType::Type::kInt64, 152 MemberOffset(10), 153 false, 154 kUnknownFieldIndex, 155 kUnknownClassDefIndex, 156 graph_->GetDexFile(), 157 0); 158 loop_body_->InsertInstructionBefore(get_field, loop_body_->GetLastInstruction()); 159 HInstruction* set_field = new (GetAllocator()) HInstanceFieldSet(parameter_, 160 get_field, 161 nullptr, 162 DataType::Type::kInt64, 163 MemberOffset(10), 164 false, 165 kUnknownFieldIndex, 166 kUnknownClassDefIndex, 167 graph_->GetDexFile(), 168 0); 169 loop_body_->InsertInstructionBefore(set_field, loop_body_->GetLastInstruction()); 170 171 EXPECT_EQ(get_field->GetBlock(), loop_body_); 172 EXPECT_EQ(set_field->GetBlock(), loop_body_); 173 PerformLICM(); 174 EXPECT_EQ(get_field->GetBlock(), loop_body_); 175 EXPECT_EQ(set_field->GetBlock(), loop_body_); 176 } 177 178 TEST_F(LICMTest, ArrayHoisting) { 179 BuildLoop(); 180 181 // Populate the loop with instructions: set/get array with different types. 182 HInstruction* get_array = new (GetAllocator()) HArrayGet( 183 parameter_, int_constant_, DataType::Type::kInt32, 0); 184 loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction()); 185 HInstruction* set_array = new (GetAllocator()) HArraySet( 186 parameter_, int_constant_, float_constant_, DataType::Type::kFloat32, 0); 187 loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction()); 188 189 EXPECT_EQ(get_array->GetBlock(), loop_body_); 190 EXPECT_EQ(set_array->GetBlock(), loop_body_); 191 PerformLICM(); 192 EXPECT_EQ(get_array->GetBlock(), loop_preheader_); 193 EXPECT_EQ(set_array->GetBlock(), loop_body_); 194 } 195 196 TEST_F(LICMTest, NoArrayHoisting) { 197 BuildLoop(); 198 199 // Populate the loop with instructions: set/get array with same types. 200 HInstruction* get_array = new (GetAllocator()) HArrayGet( 201 parameter_, int_constant_, DataType::Type::kFloat32, 0); 202 loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction()); 203 HInstruction* set_array = new (GetAllocator()) HArraySet( 204 parameter_, get_array, float_constant_, DataType::Type::kFloat32, 0); 205 loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction()); 206 207 EXPECT_EQ(get_array->GetBlock(), loop_body_); 208 EXPECT_EQ(set_array->GetBlock(), loop_body_); 209 PerformLICM(); 210 EXPECT_EQ(get_array->GetBlock(), loop_body_); 211 EXPECT_EQ(set_array->GetBlock(), loop_body_); 212 } 213 214 } // namespace art 215
