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