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:
LICMTest()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 
~LICMTest()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.
BuildLoop()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).
PerformLICM()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 
TEST_F(LICMTest,FieldHoisting)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 
TEST_F(LICMTest,NoFieldHoisting)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 
TEST_F(LICMTest,ArrayHoisting)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 
TEST_F(LICMTest,NoArrayHoisting)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