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 "base/arena_allocator.h"
18 #include "builder.h"
19 #include "licm.h"
20 #include "nodes.h"
21 #include "optimizing_unit_test.h"
22 #include "side_effects_analysis.h"
23 
24 namespace art {
25 
26 /**
27  * Fixture class for the LICM tests.
28  */
29 class LICMTest : public CommonCompilerTest {
30  public:
LICMTest()31   LICMTest()
32       : pool_(),
33         allocator_(&pool_),
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(&allocator_);
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 (&allocator_) HBasicBlock(graph_);
52     loop_preheader_ = new (&allocator_) HBasicBlock(graph_);
53     loop_header_ = new (&allocator_) HBasicBlock(graph_);
54     loop_body_ = new (&allocator_) HBasicBlock(graph_);
55     return_ = new (&allocator_) HBasicBlock(graph_);
56     exit_ = new (&allocator_) 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 (&allocator_) HParameterValue(graph_->GetDexFile(),
78                                                    dex::TypeIndex(0),
79                                                    0,
80                                                    Primitive::kPrimNot);
81     entry_->AddInstruction(parameter_);
82     int_constant_ = graph_->GetIntConstant(42);
83     float_constant_ = graph_->GetFloatConstant(42.0f);
84     loop_preheader_->AddInstruction(new (&allocator_) HGoto());
85     loop_header_->AddInstruction(new (&allocator_) HIf(parameter_));
86     loop_body_->AddInstruction(new (&allocator_) HGoto());
87     return_->AddInstruction(new (&allocator_) HReturnVoid());
88     exit_->AddInstruction(new (&allocator_) 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   ArenaPool pool_;
101   ArenaAllocator allocator_;
102   HGraph* graph_;
103 
104   // Specific basic blocks.
105   HBasicBlock* entry_;
106   HBasicBlock* loop_preheader_;
107   HBasicBlock* loop_header_;
108   HBasicBlock* loop_body_;
109   HBasicBlock* return_;
110   HBasicBlock* exit_;
111 
112   HInstruction* parameter_;  // "this"
113   HInstruction* int_constant_;
114   HInstruction* float_constant_;
115 };
116 
117 //
118 // The actual LICM tests.
119 //
120 
TEST_F(LICMTest,FieldHoisting)121 TEST_F(LICMTest, FieldHoisting) {
122   BuildLoop();
123 
124   // Populate the loop with instructions: set/get field with different types.
125   HInstruction* get_field = new (&allocator_) HInstanceFieldGet(parameter_,
126                                                                 nullptr,
127                                                                 Primitive::kPrimLong,
128                                                                 MemberOffset(10),
129                                                                 false,
130                                                                 kUnknownFieldIndex,
131                                                                 kUnknownClassDefIndex,
132                                                                 graph_->GetDexFile(),
133                                                                 0);
134   loop_body_->InsertInstructionBefore(get_field, loop_body_->GetLastInstruction());
135   HInstruction* set_field = new (&allocator_) HInstanceFieldSet(
136       parameter_, int_constant_, nullptr, Primitive::kPrimInt, MemberOffset(20),
137       false, kUnknownFieldIndex, kUnknownClassDefIndex, graph_->GetDexFile(), 0);
138   loop_body_->InsertInstructionBefore(set_field, loop_body_->GetLastInstruction());
139 
140   EXPECT_EQ(get_field->GetBlock(), loop_body_);
141   EXPECT_EQ(set_field->GetBlock(), loop_body_);
142   PerformLICM();
143   EXPECT_EQ(get_field->GetBlock(), loop_preheader_);
144   EXPECT_EQ(set_field->GetBlock(), loop_body_);
145 }
146 
TEST_F(LICMTest,NoFieldHoisting)147 TEST_F(LICMTest, NoFieldHoisting) {
148   BuildLoop();
149 
150   // Populate the loop with instructions: set/get field with same types.
151   ScopedNullHandle<mirror::DexCache> dex_cache;
152   HInstruction* get_field = new (&allocator_) HInstanceFieldGet(parameter_,
153                                                                 nullptr,
154                                                                 Primitive::kPrimLong,
155                                                                 MemberOffset(10),
156                                                                 false,
157                                                                 kUnknownFieldIndex,
158                                                                 kUnknownClassDefIndex,
159                                                                 graph_->GetDexFile(),
160                                                                 0);
161   loop_body_->InsertInstructionBefore(get_field, loop_body_->GetLastInstruction());
162   HInstruction* set_field = new (&allocator_) HInstanceFieldSet(parameter_,
163                                                                 get_field,
164                                                                 nullptr,
165                                                                 Primitive::kPrimLong,
166                                                                 MemberOffset(10),
167                                                                 false,
168                                                                 kUnknownFieldIndex,
169                                                                 kUnknownClassDefIndex,
170                                                                 graph_->GetDexFile(),
171                                                                 0);
172   loop_body_->InsertInstructionBefore(set_field, loop_body_->GetLastInstruction());
173 
174   EXPECT_EQ(get_field->GetBlock(), loop_body_);
175   EXPECT_EQ(set_field->GetBlock(), loop_body_);
176   PerformLICM();
177   EXPECT_EQ(get_field->GetBlock(), loop_body_);
178   EXPECT_EQ(set_field->GetBlock(), loop_body_);
179 }
180 
TEST_F(LICMTest,ArrayHoisting)181 TEST_F(LICMTest, ArrayHoisting) {
182   BuildLoop();
183 
184   // Populate the loop with instructions: set/get array with different types.
185   HInstruction* get_array = new (&allocator_) HArrayGet(
186       parameter_, int_constant_, Primitive::kPrimInt, 0);
187   loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction());
188   HInstruction* set_array = new (&allocator_) HArraySet(
189       parameter_, int_constant_, float_constant_, Primitive::kPrimFloat, 0);
190   loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction());
191 
192   EXPECT_EQ(get_array->GetBlock(), loop_body_);
193   EXPECT_EQ(set_array->GetBlock(), loop_body_);
194   PerformLICM();
195   EXPECT_EQ(get_array->GetBlock(), loop_preheader_);
196   EXPECT_EQ(set_array->GetBlock(), loop_body_);
197 }
198 
TEST_F(LICMTest,NoArrayHoisting)199 TEST_F(LICMTest, NoArrayHoisting) {
200   BuildLoop();
201 
202   // Populate the loop with instructions: set/get array with same types.
203   HInstruction* get_array = new (&allocator_) HArrayGet(
204       parameter_, int_constant_, Primitive::kPrimFloat, 0);
205   loop_body_->InsertInstructionBefore(get_array, loop_body_->GetLastInstruction());
206   HInstruction* set_array = new (&allocator_) HArraySet(
207       parameter_, get_array, float_constant_, Primitive::kPrimFloat, 0);
208   loop_body_->InsertInstructionBefore(set_array, loop_body_->GetLastInstruction());
209 
210   EXPECT_EQ(get_array->GetBlock(), loop_body_);
211   EXPECT_EQ(set_array->GetBlock(), loop_body_);
212   PerformLICM();
213   EXPECT_EQ(get_array->GetBlock(), loop_body_);
214   EXPECT_EQ(set_array->GetBlock(), loop_body_);
215 }
216 
217 }  // namespace art
218