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
24namespace art {
25
26/**
27 * Fixture class for the LICM tests.
28 */
29class LICMTest : public CommonCompilerTest {
30 public:
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
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.
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).
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
121TEST_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
147TEST_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
181TEST_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
199TEST_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