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