1 /*
2 * Copyright (C) 2014 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 #ifndef ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_
18 #define ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_
19
20 #include <memory>
21 #include <ostream>
22 #include <string_view>
23 #include <string>
24 #include <tuple>
25 #include <vector>
26 #include <variant>
27
28 #include "base/macros.h"
29 #include "base/indenter.h"
30 #include "base/malloc_arena_pool.h"
31 #include "base/scoped_arena_allocator.h"
32 #include "builder.h"
33 #include "common_compiler_test.h"
34 #include "dex/code_item_accessors-inl.h"
35 #include "dex/dex_file.h"
36 #include "dex/dex_instruction.h"
37 #include "dex/standard_dex_file.h"
38 #include "driver/dex_compilation_unit.h"
39 #include "graph_checker.h"
40 #include "gtest/gtest.h"
41 #include "handle_scope-inl.h"
42 #include "handle_scope.h"
43 #include "mirror/class_loader.h"
44 #include "mirror/dex_cache.h"
45 #include "nodes.h"
46 #include "scoped_thread_state_change.h"
47 #include "ssa_builder.h"
48 #include "ssa_liveness_analysis.h"
49
50 namespace art HIDDEN {
51
52 #define NUM_INSTRUCTIONS(...) \
53 (sizeof((uint16_t[]) {__VA_ARGS__}) /sizeof(uint16_t))
54
55 #define N_REGISTERS_CODE_ITEM(NUM_REGS, ...) \
56 { NUM_REGS, 0, 0, 0, 0, 0, NUM_INSTRUCTIONS(__VA_ARGS__), 0, __VA_ARGS__ }
57
58 #define ZERO_REGISTER_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(0, __VA_ARGS__)
59 #define ONE_REGISTER_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(1, __VA_ARGS__)
60 #define TWO_REGISTERS_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(2, __VA_ARGS__)
61 #define THREE_REGISTERS_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(3, __VA_ARGS__)
62 #define FOUR_REGISTERS_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(4, __VA_ARGS__)
63 #define FIVE_REGISTERS_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(5, __VA_ARGS__)
64 #define SIX_REGISTERS_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(6, __VA_ARGS__)
65
66 struct InstructionDumper {
67 public:
68 HInstruction* ins_;
69 };
70
71 inline bool operator==(const InstructionDumper& a, const InstructionDumper& b) {
72 return a.ins_ == b.ins_;
73 }
74 inline bool operator!=(const InstructionDumper& a, const InstructionDumper& b) {
75 return !(a == b);
76 }
77
78 inline std::ostream& operator<<(std::ostream& os, const InstructionDumper& id) {
79 if (id.ins_ == nullptr) {
80 return os << "NULL";
81 } else {
82 return os << "(" << id.ins_ << "): " << id.ins_->DumpWithArgs();
83 }
84 }
85
86 #define EXPECT_INS_EQ(a, b) EXPECT_EQ(InstructionDumper{a}, InstructionDumper{b})
87 #define EXPECT_INS_REMOVED(a) EXPECT_TRUE(IsRemoved(a)) << "Not removed: " << (InstructionDumper{a})
88 #define EXPECT_INS_RETAINED(a) EXPECT_FALSE(IsRemoved(a)) << "Removed: " << (InstructionDumper{a})
89 #define ASSERT_INS_EQ(a, b) ASSERT_EQ(InstructionDumper{a}, InstructionDumper{b})
90 #define ASSERT_INS_REMOVED(a) ASSERT_TRUE(IsRemoved(a)) << "Not removed: " << (InstructionDumper{a})
91 #define ASSERT_INS_RETAINED(a) ASSERT_FALSE(IsRemoved(a)) << "Removed: " << (InstructionDumper{a})
92
93 #define EXPECT_BLOCK_REMOVED(b) EXPECT_TRUE(IsRemoved(b)) << "Not removed: B" << b->GetBlockId()
94 #define EXPECT_BLOCK_RETAINED(b) EXPECT_FALSE(IsRemoved(b)) << "Removed: B" << b->GetBlockId()
95 #define ASSERT_BLOCK_REMOVED(b) ASSERT_TRUE(IsRemoved(b)) << "Not removed: B" << b->GetBlockId()
96 #define ASSERT_BLOCK_RETAINED(b) ASSERT_FALSE(IsRemoved(b)) << "Removed: B" << b->GetBlockId()
97
98 inline LiveInterval* BuildInterval(const size_t ranges[][2],
99 size_t number_of_ranges,
100 ScopedArenaAllocator* allocator,
101 int reg = -1,
102 HInstruction* defined_by = nullptr) {
103 LiveInterval* interval =
104 LiveInterval::MakeInterval(allocator, DataType::Type::kInt32, defined_by);
105 if (defined_by != nullptr) {
106 defined_by->SetLiveInterval(interval);
107 }
108 for (size_t i = number_of_ranges; i > 0; --i) {
109 interval->AddRange(ranges[i - 1][0], ranges[i - 1][1]);
110 }
111 interval->SetRegister(reg);
112 return interval;
113 }
114
RemoveSuspendChecks(HGraph * graph)115 inline void RemoveSuspendChecks(HGraph* graph) {
116 for (HBasicBlock* block : graph->GetBlocks()) {
117 if (block != nullptr) {
118 if (block->GetLoopInformation() != nullptr) {
119 block->GetLoopInformation()->SetSuspendCheck(nullptr);
120 }
121 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
122 HInstruction* current = it.Current();
123 if (current->IsSuspendCheck()) {
124 current->GetBlock()->RemoveInstruction(current);
125 }
126 }
127 }
128 }
129 }
130
131 class ArenaPoolAndAllocator {
132 public:
ArenaPoolAndAllocator()133 ArenaPoolAndAllocator()
134 : pool_(), allocator_(&pool_), arena_stack_(&pool_), scoped_allocator_(&arena_stack_) { }
135
GetAllocator()136 ArenaAllocator* GetAllocator() { return &allocator_; }
GetArenaStack()137 ArenaStack* GetArenaStack() { return &arena_stack_; }
GetScopedAllocator()138 ScopedArenaAllocator* GetScopedAllocator() { return &scoped_allocator_; }
139
140 private:
141 MallocArenaPool pool_;
142 ArenaAllocator allocator_;
143 ArenaStack arena_stack_;
144 ScopedArenaAllocator scoped_allocator_;
145 };
146
147 class AdjacencyListGraph {
148 public:
149 using Edge = std::pair<const std::string_view, const std::string_view>;
AdjacencyListGraph(HGraph * graph,ArenaAllocator * alloc,const std::string_view entry_name,const std::string_view exit_name,const std::vector<Edge> & adj)150 AdjacencyListGraph(
151 HGraph* graph,
152 ArenaAllocator* alloc,
153 const std::string_view entry_name,
154 const std::string_view exit_name,
155 const std::vector<Edge>& adj) : graph_(graph) {
156 auto create_block = [&]() {
157 HBasicBlock* blk = new (alloc) HBasicBlock(graph_);
158 graph_->AddBlock(blk);
159 return blk;
160 };
161 HBasicBlock* entry = create_block();
162 HBasicBlock* exit = create_block();
163 graph_->SetEntryBlock(entry);
164 graph_->SetExitBlock(exit);
165 name_to_block_.Put(entry_name, entry);
166 name_to_block_.Put(exit_name, exit);
167 for (const auto& [src, dest] : adj) {
168 HBasicBlock* src_blk = name_to_block_.GetOrCreate(src, create_block);
169 HBasicBlock* dest_blk = name_to_block_.GetOrCreate(dest, create_block);
170 src_blk->AddSuccessor(dest_blk);
171 }
172 graph_->ComputeDominanceInformation();
173 for (auto [name, blk] : name_to_block_) {
174 block_to_name_.Put(blk, name);
175 }
176 }
177
HasBlock(const HBasicBlock * blk)178 bool HasBlock(const HBasicBlock* blk) const {
179 return block_to_name_.find(blk) != block_to_name_.end();
180 }
181
GetName(const HBasicBlock * blk)182 std::string_view GetName(const HBasicBlock* blk) const {
183 return block_to_name_.Get(blk);
184 }
185
Get(const std::string_view & sv)186 HBasicBlock* Get(const std::string_view& sv) const {
187 return name_to_block_.Get(sv);
188 }
189
190 AdjacencyListGraph(AdjacencyListGraph&&) = default;
191 AdjacencyListGraph(const AdjacencyListGraph&) = default;
192 AdjacencyListGraph& operator=(AdjacencyListGraph&&) = default;
193 AdjacencyListGraph& operator=(const AdjacencyListGraph&) = default;
194
Dump(std::ostream & os)195 std::ostream& Dump(std::ostream& os) const {
196 struct Namer : public BlockNamer {
197 public:
198 explicit Namer(const AdjacencyListGraph& alg) : BlockNamer(), alg_(alg) {}
199 std::ostream& PrintName(std::ostream& os, HBasicBlock* blk) const override {
200 if (alg_.HasBlock(blk)) {
201 return os << alg_.GetName(blk) << " (" << blk->GetBlockId() << ")";
202 } else {
203 return os << "<Unnamed B" << blk->GetBlockId() << ">";
204 }
205 }
206
207 const AdjacencyListGraph& alg_;
208 };
209 Namer namer(*this);
210 return graph_->Dump(os, /* codegen_= */ nullptr, namer);
211 }
212
213 private:
214 HGraph* graph_;
215 SafeMap<const std::string_view, HBasicBlock*> name_to_block_;
216 SafeMap<const HBasicBlock*, const std::string_view> block_to_name_;
217 };
218
219 // Have a separate helper so the OptimizingCFITest can inherit it without causing
220 // multiple inheritance errors from having two gtest as a parent twice.
221 class OptimizingUnitTestHelper {
222 public:
OptimizingUnitTestHelper()223 OptimizingUnitTestHelper()
224 : pool_and_allocator_(new ArenaPoolAndAllocator()),
225 graph_(nullptr),
226 entry_block_(nullptr),
227 exit_block_(nullptr) { }
228
GetAllocator()229 ArenaAllocator* GetAllocator() { return pool_and_allocator_->GetAllocator(); }
GetArenaStack()230 ArenaStack* GetArenaStack() { return pool_and_allocator_->GetArenaStack(); }
GetScopedAllocator()231 ScopedArenaAllocator* GetScopedAllocator() { return pool_and_allocator_->GetScopedAllocator(); }
232
ResetPoolAndAllocator()233 void ResetPoolAndAllocator() {
234 pool_and_allocator_.reset(new ArenaPoolAndAllocator());
235 }
236
237 HGraph* CreateGraph(VariableSizedHandleScope* handles = nullptr) {
238 ArenaAllocator* const allocator = pool_and_allocator_->GetAllocator();
239
240 // Reserve a big array of 0s so the dex file constructor can offsets from the header.
241 static constexpr size_t kDexDataSize = 4 * KB;
242 const uint8_t* dex_data = reinterpret_cast<uint8_t*>(allocator->Alloc(kDexDataSize));
243
244 // Create the dex file based on the fake data. Call the constructor so that we can use virtual
245 // functions. Don't use the arena for the StandardDexFile otherwise the dex location leaks.
246 auto container =
247 std::make_shared<MemoryDexFileContainer>(dex_data, sizeof(StandardDexFile::Header));
248 dex_files_.emplace_back(new StandardDexFile(dex_data,
249 "no_location",
250 /*location_checksum*/ 0,
251 /*oat_dex_file*/ nullptr,
252 std::move(container)));
253
254 graph_ = new (allocator) HGraph(
255 allocator,
256 pool_and_allocator_->GetArenaStack(),
257 handles,
258 *dex_files_.back(),
259 /*method_idx*/-1,
260 kRuntimeISA);
261 return graph_;
262 }
263
264 // Create a control-flow graph from Dex instructions.
265 HGraph* CreateCFG(const std::vector<uint16_t>& data,
266 DataType::Type return_type = DataType::Type::kInt32) {
267 ScopedObjectAccess soa(Thread::Current());
268 VariableSizedHandleScope handles(soa.Self());
269 HGraph* graph = CreateGraph(&handles);
270
271 // The code item data might not aligned to 4 bytes, copy it to ensure that.
272 const size_t code_item_size = data.size() * sizeof(data.front());
273 void* aligned_data = GetAllocator()->Alloc(code_item_size);
274 memcpy(aligned_data, &data[0], code_item_size);
275 CHECK_ALIGNED(aligned_data, StandardDexFile::CodeItem::kAlignment);
276 const dex::CodeItem* code_item = reinterpret_cast<const dex::CodeItem*>(aligned_data);
277
278 {
279 const DexCompilationUnit* dex_compilation_unit =
280 new (graph->GetAllocator()) DexCompilationUnit(
281 /* class_loader= */ Handle<mirror::ClassLoader>(), // Invalid handle.
282 /* class_linker= */ nullptr,
283 graph->GetDexFile(),
284 code_item,
285 /* class_def_idx= */ DexFile::kDexNoIndex16,
286 /* method_idx= */ dex::kDexNoIndex,
287 /* access_flags= */ 0u,
288 /* verified_method= */ nullptr,
289 /* dex_cache= */ Handle<mirror::DexCache>()); // Invalid handle.
290 CodeItemDebugInfoAccessor accessor(graph->GetDexFile(), code_item, /*dex_method_idx*/ 0u);
291 HGraphBuilder builder(graph, dex_compilation_unit, accessor, return_type);
292 bool graph_built = (builder.BuildGraph() == kAnalysisSuccess);
293 return graph_built ? graph : nullptr;
294 }
295 }
296
297 // Create simple graph with "entry", "main" and "exit" blocks, return the "main" block.
298 // Adds `HGoto` to the "entry" block and `HExit` to the "exit block. Leaves "main" block empty.
299 HBasicBlock* InitEntryMainExitGraph(VariableSizedHandleScope* handles = nullptr) {
300 CreateGraph(handles);
301 entry_block_ = AddNewBlock();
302 HBasicBlock* main_block = AddNewBlock();
303 exit_block_ = AddNewBlock();
304
305 graph_->SetEntryBlock(entry_block_);
306 graph_->SetExitBlock(exit_block_);
307
308 entry_block_->AddSuccessor(main_block);
309 main_block->AddSuccessor(exit_block_);
310
311 MakeGoto(entry_block_);
312 MakeExit(exit_block_);
313
314 return main_block;
315 }
316
317 // Creates a graph identical to `InitEntryMainExitGraph()` and adds `HReturnVoid`.
318 HBasicBlock* InitEntryMainExitGraphWithReturnVoid(VariableSizedHandleScope* handles = nullptr) {
319 HBasicBlock* return_block = InitEntryMainExitGraph(handles);
320 MakeReturnVoid(return_block);
321 return return_block;
322 }
323
324 // Insert "if_block", "then_block" and "else_block" before a given `merge_block`. Return the
325 // new blocks. Adds `HGoto` to "then_block" and "else_block". Adds `HIf` to the "if_block"
326 // if the caller provides a `condition`.
327 std::tuple<HBasicBlock*, HBasicBlock*, HBasicBlock*> CreateDiamondPattern(
328 HBasicBlock* merge_block, HInstruction* condition = nullptr) {
329 HBasicBlock* if_block = AddNewBlock();
330 HBasicBlock* then_block = AddNewBlock();
331 HBasicBlock* else_block = AddNewBlock();
332
333 HBasicBlock* predecessor = merge_block->GetSinglePredecessor();
334 predecessor->ReplaceSuccessor(merge_block, if_block);
335
336 if_block->AddSuccessor(then_block);
337 if_block->AddSuccessor(else_block);
338 then_block->AddSuccessor(merge_block);
339 else_block->AddSuccessor(merge_block);
340
341 if (condition != nullptr) {
342 MakeIf(if_block, condition);
343 }
344 MakeGoto(then_block);
345 MakeGoto(else_block);
346
347 return {if_block, then_block, else_block};
348 }
349
350 // Insert "pre-header", "loop-header" and "loop-body" blocks before a given `loop_exit` block
351 // and connect them in a `while (...) { ... }` loop pattern. Return the new blocks.
352 // Adds `HGoto` to the "pre-header" and "loop-body" blocks but leaves the "loop-header" block
353 // empty, leaving the construction of an appropriate condition and `HIf` to the caller.
354 // Note: The `loop_exit` shall be the "then" successor of the "loop-header". If the `loop_exit`
355 // is needed as the "else" successor, use `HBlock::SwapSuccessors()` to adjust the order.
356 // Note: A `do { ... } while (...);` loop pattern has the same block structure, except that
357 // the `loop_body` is a single-goto block that exists purely to avoid a critical edge.
CreateWhileLoop(HBasicBlock * loop_exit)358 std::tuple<HBasicBlock*, HBasicBlock*, HBasicBlock*> CreateWhileLoop(HBasicBlock* loop_exit) {
359 HBasicBlock* pre_header = AddNewBlock();
360 HBasicBlock* loop_header = AddNewBlock();
361 HBasicBlock* loop_body = AddNewBlock();
362
363 HBasicBlock* predecessor = loop_exit->GetSinglePredecessor();
364 predecessor->ReplaceSuccessor(loop_exit, pre_header);
365
366 pre_header->AddSuccessor(loop_header);
367 loop_header->AddSuccessor(loop_exit); // true successor
368 loop_header->AddSuccessor(loop_body); // false successor
369 loop_body->AddSuccessor(loop_header);
370
371 MakeGoto(pre_header);
372 MakeGoto(loop_body);
373
374 return {pre_header, loop_header, loop_body};
375 }
376
377 // Insert blocks for an irreducible loop before the `loop_exit`:
378 //
379 // <loop_exit's old predecessor>
380 // |
381 // split
382 // / \
383 // left_preheader right_preheader
384 // | |
385 // left_header <------- right_header <-+
386 // | | |
387 // | +------------> body ------------+
388 // |
389 // loop_exit
390 //
391 // Note that `left_preheader`, `right_preheader` and `body` are needed to avoid critical edges.
392 //
393 // `HGoto` instructions are added to `left_preheader`, `right_preheader`, `body`
394 // and `right_header`. To complete the control flow, the caller should add `HIf`
395 // to `split` and `left_header`.
396 //
397 // Returns `{split, left_header, right_header, body}`.
CreateIrreducibleLoop(HBasicBlock * loop_exit)398 std::tuple<HBasicBlock*, HBasicBlock*, HBasicBlock*, HBasicBlock*> CreateIrreducibleLoop(
399 HBasicBlock* loop_exit) {
400 HBasicBlock* split = AddNewBlock();
401 HBasicBlock* left_preheader = AddNewBlock();
402 HBasicBlock* right_preheader = AddNewBlock();
403 HBasicBlock* left_header = AddNewBlock();
404 HBasicBlock* right_header = AddNewBlock();
405 HBasicBlock* body = AddNewBlock();
406
407 HBasicBlock* predecessor = loop_exit->GetSinglePredecessor();
408 predecessor->ReplaceSuccessor(loop_exit, split);
409
410 split->AddSuccessor(left_preheader); // true successor
411 split->AddSuccessor(right_preheader); // false successor
412 left_preheader->AddSuccessor(left_header);
413 right_preheader->AddSuccessor(right_header);
414 left_header->AddSuccessor(loop_exit); // true successor
415 left_header->AddSuccessor(body); // false successor
416 body->AddSuccessor(right_header);
417 right_header->AddSuccessor(left_header);
418
419 MakeGoto(left_preheader);
420 MakeGoto(right_preheader);
421 MakeGoto(body);
422 MakeGoto(right_header);
423
424 return {split, left_header, right_header, body};
425 }
426
AddNewBlock()427 HBasicBlock* AddNewBlock() {
428 HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph_);
429 graph_->AddBlock(block);
430 return block;
431 }
432
433 // Run GraphChecker with all checks.
434 //
435 // Return: the status whether the run is successful.
436 bool CheckGraph(std::ostream& oss = std::cerr) {
437 return CheckGraph(graph_, oss);
438 }
439
ManuallyBuildEnvFor(HInstruction * instruction,ArenaVector<HInstruction * > * current_locals)440 HEnvironment* ManuallyBuildEnvFor(HInstruction* instruction,
441 ArenaVector<HInstruction*>* current_locals) {
442 HEnvironment* environment = HEnvironment::Create(
443 GetAllocator(),
444 current_locals->size(),
445 graph_->GetArtMethod(),
446 instruction->GetDexPc(),
447 instruction);
448
449 environment->CopyFrom(GetAllocator(), ArrayRef<HInstruction* const>(*current_locals));
450 instruction->SetRawEnvironment(environment);
451 return environment;
452 }
453
EnsurePredecessorOrder(HBasicBlock * target,std::initializer_list<HBasicBlock * > preds)454 void EnsurePredecessorOrder(HBasicBlock* target, std::initializer_list<HBasicBlock*> preds) {
455 // Make sure the given preds and block predecessors have the same blocks.
456 BitVector bv(preds.size(), false, Allocator::GetCallocAllocator());
457 auto preds_and_idx = ZipCount(MakeIterationRange(target->GetPredecessors()));
458 bool correct_preds = preds.size() == target->GetPredecessors().size() &&
459 std::all_of(preds.begin(), preds.end(), [&](HBasicBlock* pred) {
460 return std::any_of(preds_and_idx.begin(),
461 preds_and_idx.end(),
462 // Make sure every target predecessor is used only
463 // once.
464 [&](std::pair<HBasicBlock*, uint32_t> cur) {
465 if (cur.first == pred && !bv.IsBitSet(cur.second)) {
466 bv.SetBit(cur.second);
467 return true;
468 } else {
469 return false;
470 }
471 });
472 }) &&
473 bv.NumSetBits() == preds.size();
474 auto dump_list = [](auto it) {
475 std::ostringstream oss;
476 oss << "[";
477 bool first = true;
478 for (HBasicBlock* b : it) {
479 if (!first) {
480 oss << ", ";
481 }
482 first = false;
483 oss << b->GetBlockId();
484 }
485 oss << "]";
486 return oss.str();
487 };
488 ASSERT_TRUE(correct_preds) << "Predecessors of " << target->GetBlockId() << " are "
489 << dump_list(target->GetPredecessors()) << " not "
490 << dump_list(preds);
491 if (correct_preds) {
492 std::copy(preds.begin(), preds.end(), target->predecessors_.begin());
493 }
494 }
495
SetupFromAdjacencyList(const std::string_view entry_name,const std::string_view exit_name,const std::vector<AdjacencyListGraph::Edge> & adj)496 AdjacencyListGraph SetupFromAdjacencyList(const std::string_view entry_name,
497 const std::string_view exit_name,
498 const std::vector<AdjacencyListGraph::Edge>& adj) {
499 return AdjacencyListGraph(graph_, GetAllocator(), entry_name, exit_name, adj);
500 }
501
ManuallyBuildEnvFor(HInstruction * ins,const std::initializer_list<HInstruction * > & env)502 void ManuallyBuildEnvFor(HInstruction* ins, const std::initializer_list<HInstruction*>& env) {
503 ArenaVector<HInstruction*> current_locals(env, GetAllocator()->Adapter(kArenaAllocInstruction));
504 OptimizingUnitTestHelper::ManuallyBuildEnvFor(ins, ¤t_locals);
505 }
506
507 HLoadClass* MakeLoadClass(HBasicBlock* block,
508 std::optional<dex::TypeIndex> ti = std::nullopt,
509 std::optional<Handle<mirror::Class>> klass = std::nullopt,
510 std::initializer_list<HInstruction*> env = {},
511 uint32_t dex_pc = kNoDexPc) {
512 HLoadClass* load_class = new (GetAllocator()) HLoadClass(
513 graph_->GetCurrentMethod(),
514 ti ? *ti : dex::TypeIndex(class_idx_++),
515 graph_->GetDexFile(),
516 /* klass= */ klass ? *klass : null_klass_,
517 /* is_referrers_class= */ false,
518 dex_pc,
519 /* needs_access_check= */ false);
520 AddOrInsertInstruction(block, load_class);
521 ManuallyBuildEnvFor(load_class, env);
522 return load_class;
523 }
524
525 HNewInstance* MakeNewInstance(HBasicBlock* block,
526 HInstruction* cls,
527 std::initializer_list<HInstruction*> env = {},
528 uint32_t dex_pc = kNoDexPc) {
529 EXPECT_TRUE(cls->IsLoadClass() || cls->IsClinitCheck()) << *cls;
530 HLoadClass* load =
531 cls->IsLoadClass() ? cls->AsLoadClass() : cls->AsClinitCheck()->GetLoadClass();
532 HNewInstance* new_instance = new (GetAllocator()) HNewInstance(
533 cls,
534 dex_pc,
535 load->GetTypeIndex(),
536 graph_->GetDexFile(),
537 /* finalizable= */ false,
538 QuickEntrypointEnum::kQuickAllocObjectInitialized);
539 AddOrInsertInstruction(block, new_instance);
540 ManuallyBuildEnvFor(new_instance, env);
541 return new_instance;
542 }
543
544 HInstanceFieldSet* MakeIFieldSet(HBasicBlock* block,
545 HInstruction* object,
546 HInstruction* data,
547 MemberOffset off,
548 uint32_t dex_pc = kNoDexPc) {
549 CHECK(data != nullptr);
550 return MakeIFieldSet(block, object, data, data->GetType(), off, dex_pc);
551 }
552
553 HInstanceFieldSet* MakeIFieldSet(HBasicBlock* block,
554 HInstruction* object,
555 HInstruction* data,
556 DataType::Type field_type,
557 MemberOffset off,
558 uint32_t dex_pc = kNoDexPc) {
559 HInstanceFieldSet* ifield_set = new (GetAllocator()) HInstanceFieldSet(
560 object,
561 data,
562 /* field= */ nullptr,
563 field_type,
564 /* field_offset= */ off,
565 /* is_volatile= */ false,
566 kUnknownFieldIndex,
567 kUnknownClassDefIndex,
568 graph_->GetDexFile(),
569 dex_pc);
570 AddOrInsertInstruction(block, ifield_set);
571 return ifield_set;
572 }
573
574 HInstanceFieldGet* MakeIFieldGet(HBasicBlock* block,
575 HInstruction* object,
576 DataType::Type type,
577 MemberOffset off,
578 uint32_t dex_pc = kNoDexPc) {
579 HInstanceFieldGet* ifield_get = new (GetAllocator()) HInstanceFieldGet(
580 object,
581 /* field= */ nullptr,
582 /* field_type= */ type,
583 /* field_offset= */ off,
584 /* is_volatile= */ false,
585 kUnknownFieldIndex,
586 kUnknownClassDefIndex,
587 graph_->GetDexFile(),
588 dex_pc);
589 AddOrInsertInstruction(block, ifield_get);
590 return ifield_get;
591 }
592
593 HNewArray* MakeNewArray(HBasicBlock* block,
594 HInstruction* cls,
595 HInstruction* length,
596 size_t component_size_shift = DataType::SizeShift(DataType::Type::kInt32),
597 std::initializer_list<HInstruction*> env = {},
598 uint32_t dex_pc = kNoDexPc) {
599 HNewArray* new_array =
600 new (GetAllocator()) HNewArray(cls, length, dex_pc, component_size_shift);
601 AddOrInsertInstruction(block, new_array);
602 ManuallyBuildEnvFor(new_array, env);
603 return new_array;
604 }
605
606 HArraySet* MakeArraySet(HBasicBlock* block,
607 HInstruction* array,
608 HInstruction* index,
609 HInstruction* value,
610 uint32_t dex_pc = kNoDexPc) {
611 CHECK(value != nullptr);
612 return MakeArraySet(block, array, index, value, value->GetType(), dex_pc);
613 }
614
615 HArraySet* MakeArraySet(HBasicBlock* block,
616 HInstruction* array,
617 HInstruction* index,
618 HInstruction* value,
619 DataType::Type type,
620 uint32_t dex_pc = kNoDexPc) {
621 HArraySet* array_set = new (GetAllocator()) HArraySet(array, index, value, type, dex_pc);
622 AddOrInsertInstruction(block, array_set);
623 return array_set;
624 }
625
626 HArrayGet* MakeArrayGet(HBasicBlock* block,
627 HInstruction* array,
628 HInstruction* index,
629 DataType::Type type,
630 uint32_t dex_pc = kNoDexPc) {
631 HArrayGet* array_get = new (GetAllocator()) HArrayGet(array, index, type, dex_pc);
632 AddOrInsertInstruction(block, array_get);
633 return array_get;
634 }
635
636 HArrayLength* MakeArrayLength(HBasicBlock* block,
637 HInstruction* array,
638 uint32_t dex_pc = kNoDexPc) {
639 HArrayLength* array_length = new (GetAllocator()) HArrayLength(array, dex_pc);
640 AddOrInsertInstruction(block, array_length);
641 return array_length;
642 }
643
644 HNullCheck* MakeNullCheck(HBasicBlock* block,
645 HInstruction* value,
646 std::initializer_list<HInstruction*> env = {},
647 uint32_t dex_pc = kNoDexPc) {
648 HNullCheck* null_check = new (GetAllocator()) HNullCheck(value, dex_pc);
649 AddOrInsertInstruction(block, null_check);
650 ManuallyBuildEnvFor(null_check, env);
651 return null_check;
652 }
653
654 HBoundsCheck* MakeBoundsCheck(HBasicBlock* block,
655 HInstruction* index,
656 HInstruction* length,
657 std::initializer_list<HInstruction*> env = {},
658 uint32_t dex_pc = kNoDexPc) {
659 HBoundsCheck* bounds_check = new (GetAllocator()) HBoundsCheck(index, length, dex_pc);
660 AddOrInsertInstruction(block, bounds_check);
661 ManuallyBuildEnvFor(bounds_check, env);
662 return bounds_check;
663 }
664
665 HVecStore* MakeVecStore(HBasicBlock* block,
666 HInstruction* base,
667 HInstruction* index,
668 HInstruction* value,
669 DataType::Type packed_type,
670 size_t vector_size_in_bytes = kDefaultTestVectorSizeInBytes,
671 uint32_t dex_pc = kNoDexPc) {
672 size_t num_of_elements = GetNumberOfElementsInVector(vector_size_in_bytes, packed_type);
673 SideEffects side_effects = SideEffects::ArrayWriteOfType(packed_type);
674 HVecStore* vec_store = new (GetAllocator()) HVecStore(
675 GetAllocator(), base, index, value, packed_type, side_effects, num_of_elements, dex_pc);
676 AddOrInsertInstruction(block, vec_store);
677 return vec_store;
678 }
679
680 HVecPredSetAll* MakeVecPredSetAll(HBasicBlock* block,
681 HInstruction* input,
682 DataType::Type packed_type,
683 size_t vector_size_in_bytes = kDefaultTestVectorSizeInBytes,
684 uint32_t dex_pc = kNoDexPc) {
685 size_t num_of_elements = GetNumberOfElementsInVector(vector_size_in_bytes, packed_type);
686 HVecPredSetAll* predicate = new (GetAllocator()) HVecPredSetAll(
687 GetAllocator(), input, packed_type, num_of_elements, dex_pc);
688 AddOrInsertInstruction(block, predicate);
689 return predicate;
690 }
691
692 HVecReplicateScalar* MakeVecReplicateScalar(
693 HBasicBlock* block,
694 HInstruction* scalar,
695 DataType::Type packed_type,
696 size_t vector_size_in_bytes = kDefaultTestVectorSizeInBytes,
697 HVecPredSetOperation* predicate = nullptr,
698 uint32_t dex_pc = kNoDexPc) {
699 size_t num_of_elements = GetNumberOfElementsInVector(vector_size_in_bytes, packed_type);
700 HVecReplicateScalar* vec_replicate_scalar = new (GetAllocator()) HVecReplicateScalar(
701 GetAllocator(), scalar, packed_type, num_of_elements, dex_pc);
702 AddOrInsertInstruction(block, vec_replicate_scalar);
703 if (predicate != nullptr) {
704 vec_replicate_scalar->SetMergingGoverningPredicate(predicate);
705 }
706 return vec_replicate_scalar;
707 }
708
709 HVecPredToBoolean* MakeVecPredToBoolean(
710 HBasicBlock* block,
711 HInstruction* input,
712 HVecPredToBoolean::PCondKind pred_cond,
713 DataType::Type packed_type,
714 size_t vector_size_in_bytes = kDefaultTestVectorSizeInBytes,
715 uint32_t dex_pc = kNoDexPc) {
716 size_t num_of_elements = GetNumberOfElementsInVector(vector_size_in_bytes, packed_type);
717 HVecPredToBoolean* vec_pred_to_boolean = new (GetAllocator()) HVecPredToBoolean(
718 GetAllocator(),
719 input,
720 pred_cond,
721 packed_type,
722 num_of_elements,
723 dex_pc);
724 AddOrInsertInstruction(block, vec_pred_to_boolean);
725 return vec_pred_to_boolean;
726 }
727
728 HVecPredWhile* MakeVecPredWhile(HBasicBlock* block,
729 HInstruction* left,
730 HInstruction* right,
731 HVecPredWhile::CondKind cond,
732 DataType::Type packed_type,
733 size_t vector_size_in_bytes = kDefaultTestVectorSizeInBytes,
734 uint32_t dex_pc = kNoDexPc) {
735 size_t num_of_elements = GetNumberOfElementsInVector(vector_size_in_bytes, packed_type);
736 HVecPredWhile* vec_pred_while = new (GetAllocator()) HVecPredWhile(
737 GetAllocator(),
738 left,
739 right,
740 cond,
741 packed_type,
742 num_of_elements,
743 dex_pc);
744 AddOrInsertInstruction(block, vec_pred_while);
745 return vec_pred_while;
746 }
747
748 HInvokeStaticOrDirect* MakeInvokeStatic(HBasicBlock* block,
749 DataType::Type return_type,
750 const std::vector<HInstruction*>& args,
751 std::initializer_list<HInstruction*> env = {},
752 uint32_t dex_pc = kNoDexPc) {
753 MethodReference method_reference{/* file= */ &graph_->GetDexFile(), /* index= */ method_idx_++};
754 size_t num_64bit_args = std::count_if(args.begin(), args.end(), [](HInstruction* insn) {
755 return DataType::Is64BitType(insn->GetType());
756 });
757 HInvokeStaticOrDirect* invoke = new (GetAllocator())
758 HInvokeStaticOrDirect(GetAllocator(),
759 args.size(),
760 /* number_of_out_vregs= */ args.size() + num_64bit_args,
761 return_type,
762 dex_pc,
763 method_reference,
764 /* resolved_method= */ nullptr,
765 HInvokeStaticOrDirect::DispatchInfo{},
766 InvokeType::kStatic,
767 /* resolved_method_reference= */ method_reference,
768 HInvokeStaticOrDirect::ClinitCheckRequirement::kNone,
769 !graph_->IsDebuggable());
770 for (auto [ins, idx] : ZipCount(MakeIterationRange(args))) {
771 invoke->SetRawInputAt(idx, ins);
772 }
773 AddOrInsertInstruction(block, invoke);
774 ManuallyBuildEnvFor(invoke, env);
775 return invoke;
776 }
777
778 template <typename Type>
779 Type* MakeBinOp(HBasicBlock* block,
780 DataType::Type result_type,
781 HInstruction* left,
782 HInstruction* right,
783 uint32_t dex_pc = kNoDexPc) {
784 static_assert(std::is_base_of_v<HBinaryOperation, Type>);
785 Type* insn = new (GetAllocator()) Type(result_type, left, right, dex_pc);
786 AddOrInsertInstruction(block, insn);
787 return insn;
788 }
789
790 HCondition* MakeCondition(HBasicBlock* block,
791 IfCondition cond,
792 HInstruction* first,
793 HInstruction* second,
794 uint32_t dex_pc = kNoDexPc) {
795 HCondition* condition = HCondition::Create(graph_, cond, first, second, dex_pc);
796 AddOrInsertInstruction(block, condition);
797 return condition;
798 }
799
800 HVecCondition* MakeVecCondition(HBasicBlock* block,
801 IfCondition cond,
802 HInstruction* first,
803 HInstruction* second,
804 DataType::Type packed_type,
805 size_t vector_size_in_bytes = kDefaultTestVectorSizeInBytes,
806 HVecPredSetOperation* predicate = nullptr,
807 uint32_t dex_pc = kNoDexPc) {
808 size_t num_of_elements = GetNumberOfElementsInVector(vector_size_in_bytes, packed_type);
809 HVecCondition* condition = HVecCondition::Create(graph_,
810 cond,
811 first,
812 second,
813 packed_type,
814 num_of_elements,
815 dex_pc);
816 AddOrInsertInstruction(block, condition);
817 if (predicate != nullptr) {
818 condition->SetMergingGoverningPredicate(predicate);
819 }
820 return condition;
821 }
822
823 HSelect* MakeSelect(HBasicBlock* block,
824 HInstruction* condition,
825 HInstruction* true_value,
826 HInstruction* false_value,
827 uint32_t dex_pc = kNoDexPc) {
828 HSelect* select = new (GetAllocator()) HSelect(condition, true_value, false_value, dex_pc);
829 AddOrInsertInstruction(block, select);
830 return select;
831 }
832
833 HSuspendCheck* MakeSuspendCheck(HBasicBlock* block,
834 std::initializer_list<HInstruction*> env = {},
835 uint32_t dex_pc = kNoDexPc) {
836 HSuspendCheck* suspend_check = new (GetAllocator()) HSuspendCheck(dex_pc);
837 AddOrInsertInstruction(block, suspend_check);
838 ManuallyBuildEnvFor(suspend_check, env);
839 return suspend_check;
840 }
841
AddOrInsertInstruction(HBasicBlock * block,HInstruction * instruction)842 void AddOrInsertInstruction(HBasicBlock* block, HInstruction* instruction) {
843 CHECK(!instruction->IsControlFlow());
844 if (block->GetLastInstruction() != nullptr && block->GetLastInstruction()->IsControlFlow()) {
845 block->InsertInstructionBefore(instruction, block->GetLastInstruction());
846 } else {
847 block->AddInstruction(instruction);
848 }
849 }
850
851 HIf* MakeIf(HBasicBlock* block, HInstruction* cond, uint32_t dex_pc = kNoDexPc) {
852 HIf* if_insn = new (GetAllocator()) HIf(cond, dex_pc);
853 block->AddInstruction(if_insn);
854 return if_insn;
855 }
856
857 HGoto* MakeGoto(HBasicBlock* block, uint32_t dex_pc = kNoDexPc) {
858 HGoto* goto_insn = new (GetAllocator()) HGoto(dex_pc);
859 block->AddInstruction(goto_insn);
860 return goto_insn;
861 }
862
863 HReturnVoid* MakeReturnVoid(HBasicBlock* block, uint32_t dex_pc = kNoDexPc) {
864 HReturnVoid* return_void = new (GetAllocator()) HReturnVoid(dex_pc);
865 block->AddInstruction(return_void);
866 return return_void;
867 }
868
869 HReturn* MakeReturn(HBasicBlock* block, HInstruction* value, uint32_t dex_pc = kNoDexPc) {
870 HReturn* return_insn = new (GetAllocator()) HReturn(value, dex_pc);
871 block->AddInstruction(return_insn);
872 return return_insn;
873 }
874
MakeExit(HBasicBlock * exit_block)875 HExit* MakeExit(HBasicBlock* exit_block) {
876 HExit* exit = new (GetAllocator()) HExit();
877 exit_block->AddInstruction(exit);
878 return exit;
879 }
880
MakePhi(HBasicBlock * block,const std::vector<HInstruction * > & ins)881 HPhi* MakePhi(HBasicBlock* block, const std::vector<HInstruction*>& ins) {
882 EXPECT_GE(ins.size(), 2u) << "Phi requires at least 2 inputs";
883 DataType::Type type = DataType::Kind(ins[0]->GetType());
884 HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), kNoRegNumber, ins.size(), type);
885 for (auto [i, idx] : ZipCount(MakeIterationRange(ins))) {
886 phi->SetRawInputAt(idx, i);
887 }
888 block->AddPhi(phi);
889 return phi;
890 }
891
MakeLinearLoopVar(HBasicBlock * header,HBasicBlock * body,int32_t initial,int32_t increment)892 std::tuple<HPhi*, HAdd*> MakeLinearLoopVar(HBasicBlock* header,
893 HBasicBlock* body,
894 int32_t initial,
895 int32_t increment) {
896 HInstruction* initial_const = graph_->GetIntConstant(initial);
897 HInstruction* increment_const = graph_->GetIntConstant(increment);
898 return MakeLinearLoopVar(header, body, initial_const, increment_const);
899 }
900
MakeLinearLoopVar(HBasicBlock * header,HBasicBlock * body,HInstruction * initial,HInstruction * increment)901 std::tuple<HPhi*, HAdd*> MakeLinearLoopVar(HBasicBlock* header,
902 HBasicBlock* body,
903 HInstruction* initial,
904 HInstruction* increment) {
905 HPhi* phi = MakePhi(header, {initial, /* placeholder */ initial});
906 HAdd* add = MakeBinOp<HAdd>(body, phi->GetType(), phi, increment);
907 phi->ReplaceInput(add, 1u); // Update back-edge input.
908 return {phi, add};
909 }
910
MakeLinearIrreducibleLoopVar(HBasicBlock * left_header,HBasicBlock * right_header,HBasicBlock * body,HInstruction * left_initial,HInstruction * right_initial,HInstruction * increment)911 std::tuple<HPhi*, HPhi*, HAdd*> MakeLinearIrreducibleLoopVar(HBasicBlock* left_header,
912 HBasicBlock* right_header,
913 HBasicBlock* body,
914 HInstruction* left_initial,
915 HInstruction* right_initial,
916 HInstruction* increment) {
917 HPhi* left_phi = MakePhi(left_header, {left_initial, /* placeholder */ left_initial});
918 HAdd* add = MakeBinOp<HAdd>(body, left_phi->GetType(), left_phi, increment);
919 HPhi* right_phi = MakePhi(right_header, {right_initial, add});
920 left_phi->ReplaceInput(right_phi, 1u); // Update back-edge input.
921 return {left_phi, right_phi, add};
922 }
923
DefaultTypeIndexForType(DataType::Type type)924 dex::TypeIndex DefaultTypeIndexForType(DataType::Type type) {
925 switch (type) {
926 case DataType::Type::kBool:
927 return dex::TypeIndex(1);
928 case DataType::Type::kUint8:
929 case DataType::Type::kInt8:
930 return dex::TypeIndex(2);
931 case DataType::Type::kUint16:
932 case DataType::Type::kInt16:
933 return dex::TypeIndex(3);
934 case DataType::Type::kUint32:
935 case DataType::Type::kInt32:
936 return dex::TypeIndex(4);
937 case DataType::Type::kUint64:
938 case DataType::Type::kInt64:
939 return dex::TypeIndex(5);
940 case DataType::Type::kReference:
941 return dex::TypeIndex(6);
942 case DataType::Type::kFloat32:
943 return dex::TypeIndex(7);
944 case DataType::Type::kFloat64:
945 return dex::TypeIndex(8);
946 case DataType::Type::kVoid:
947 EXPECT_TRUE(false) << "No type for void!";
948 return dex::TypeIndex(1000);
949 }
950 }
951
952 // Creates a parameter. The instruction is automatically added to the entry-block.
953 HParameterValue* MakeParam(DataType::Type type, std::optional<dex::TypeIndex> ti = std::nullopt) {
954 HParameterValue* val = new (GetAllocator()) HParameterValue(
955 graph_->GetDexFile(), ti ? *ti : DefaultTypeIndexForType(type), param_count_++, type);
956 AddOrInsertInstruction(graph_->GetEntryBlock(), val);
957 return val;
958 }
959
PredecessorsEqual(HBasicBlock * block,std::initializer_list<HBasicBlock * > expected)960 static bool PredecessorsEqual(HBasicBlock* block,
961 std::initializer_list<HBasicBlock*> expected) {
962 return RangeEquals(block->GetPredecessors(), expected);
963 }
964
InputsEqual(HInstruction * instruction,std::initializer_list<HInstruction * > expected)965 static bool InputsEqual(HInstruction* instruction,
966 std::initializer_list<HInstruction*> expected) {
967 return RangeEquals(instruction->GetInputs(), expected);
968 }
969
970 // Returns if the `instruction` is removed from the graph.
IsRemoved(HInstruction * instruction)971 static inline bool IsRemoved(HInstruction* instruction) {
972 return instruction->GetBlock() == nullptr;
973 }
974
975 // Returns if the `block` is removed from the graph.
IsRemoved(HBasicBlock * block)976 static inline bool IsRemoved(HBasicBlock* block) {
977 return block->GetGraph() == nullptr;
978 }
979
980 protected:
CheckGraph(HGraph * graph,std::ostream & oss)981 bool CheckGraph(HGraph* graph, std::ostream& oss) {
982 GraphChecker checker(graph);
983 checker.Run();
984 checker.Dump(oss);
985 return checker.IsValid();
986 }
987
988 template <typename Range, typename ElementType>
RangeEquals(Range && range,std::initializer_list<ElementType> expected)989 static bool RangeEquals(Range&& range, std::initializer_list<ElementType> expected) {
990 return std::distance(range.begin(), range.end()) == expected.size() &&
991 std::equal(range.begin(), range.end(), expected.begin());
992 }
993
994 std::vector<std::unique_ptr<const StandardDexFile>> dex_files_;
995 std::unique_ptr<ArenaPoolAndAllocator> pool_and_allocator_;
996
997 HGraph* graph_;
998 HBasicBlock* entry_block_;
999 HBasicBlock* exit_block_;
1000
1001 size_t param_count_ = 0;
1002 size_t class_idx_ = 42;
1003 uint32_t method_idx_ = 100;
1004
1005 // The default size of vectors to use for tests, in bytes. 16 bytes (128 bits) is used as it is
1006 // commonly the smallest size of vector used in vector extensions.
1007 static constexpr size_t kDefaultTestVectorSizeInBytes = 16;
1008
1009 ScopedNullHandle<mirror::Class> null_klass_;
1010 };
1011
1012 class OptimizingUnitTest : public CommonArtTest, public OptimizingUnitTestHelper {};
1013
1014 // Naive string diff data type.
1015 using diff_t = std::list<std::pair<std::string, std::string>>;
1016
1017 // An alias for the empty string used to make it clear that a line is
1018 // removed in a diff.
1019 static const std::string removed = ""; // NOLINT [runtime/string] [4]
1020
1021 // Naive patch command: apply a diff to a string.
Patch(const std::string & original,const diff_t & diff)1022 inline std::string Patch(const std::string& original, const diff_t& diff) {
1023 std::string result = original;
1024 for (const auto& p : diff) {
1025 std::string::size_type pos = result.find(p.first);
1026 DCHECK_NE(pos, std::string::npos)
1027 << "Could not find: \"" << p.first << "\" in \"" << result << "\"";
1028 result.replace(pos, p.first.size(), p.second);
1029 }
1030 return result;
1031 }
1032
1033 inline std::ostream& operator<<(std::ostream& oss, const AdjacencyListGraph& alg) {
1034 return alg.Dump(oss);
1035 }
1036
1037 } // namespace art
1038
1039 #endif // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_
1040