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 <vector>
22 
23 #include "base/malloc_arena_pool.h"
24 #include "base/scoped_arena_allocator.h"
25 #include "builder.h"
26 #include "common_compiler_test.h"
27 #include "dex/code_item_accessors-inl.h"
28 #include "dex/dex_file.h"
29 #include "dex/dex_instruction.h"
30 #include "dex/standard_dex_file.h"
31 #include "driver/dex_compilation_unit.h"
32 #include "graph_checker.h"
33 #include "handle_scope-inl.h"
34 #include "mirror/class_loader.h"
35 #include "mirror/dex_cache.h"
36 #include "nodes.h"
37 #include "scoped_thread_state_change.h"
38 #include "ssa_builder.h"
39 #include "ssa_liveness_analysis.h"
40 
41 #include "gtest/gtest.h"
42 
43 namespace art {
44 
45 #define NUM_INSTRUCTIONS(...)  \
46   (sizeof((uint16_t[]) {__VA_ARGS__}) /sizeof(uint16_t))
47 
48 #define N_REGISTERS_CODE_ITEM(NUM_REGS, ...)                            \
49     { NUM_REGS, 0, 0, 0, 0, 0, NUM_INSTRUCTIONS(__VA_ARGS__), 0, __VA_ARGS__ }
50 
51 #define ZERO_REGISTER_CODE_ITEM(...)   N_REGISTERS_CODE_ITEM(0, __VA_ARGS__)
52 #define ONE_REGISTER_CODE_ITEM(...)    N_REGISTERS_CODE_ITEM(1, __VA_ARGS__)
53 #define TWO_REGISTERS_CODE_ITEM(...)   N_REGISTERS_CODE_ITEM(2, __VA_ARGS__)
54 #define THREE_REGISTERS_CODE_ITEM(...) N_REGISTERS_CODE_ITEM(3, __VA_ARGS__)
55 #define FOUR_REGISTERS_CODE_ITEM(...)  N_REGISTERS_CODE_ITEM(4, __VA_ARGS__)
56 #define FIVE_REGISTERS_CODE_ITEM(...)  N_REGISTERS_CODE_ITEM(5, __VA_ARGS__)
57 #define SIX_REGISTERS_CODE_ITEM(...)   N_REGISTERS_CODE_ITEM(6, __VA_ARGS__)
58 
59 LiveInterval* BuildInterval(const size_t ranges[][2],
60                             size_t number_of_ranges,
61                             ScopedArenaAllocator* allocator,
62                             int reg = -1,
63                             HInstruction* defined_by = nullptr) {
64   LiveInterval* interval =
65       LiveInterval::MakeInterval(allocator, DataType::Type::kInt32, defined_by);
66   if (defined_by != nullptr) {
67     defined_by->SetLiveInterval(interval);
68   }
69   for (size_t i = number_of_ranges; i > 0; --i) {
70     interval->AddRange(ranges[i - 1][0], ranges[i - 1][1]);
71   }
72   interval->SetRegister(reg);
73   return interval;
74 }
75 
RemoveSuspendChecks(HGraph * graph)76 void RemoveSuspendChecks(HGraph* graph) {
77   for (HBasicBlock* block : graph->GetBlocks()) {
78     if (block != nullptr) {
79       if (block->GetLoopInformation() != nullptr) {
80         block->GetLoopInformation()->SetSuspendCheck(nullptr);
81       }
82       for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
83         HInstruction* current = it.Current();
84         if (current->IsSuspendCheck()) {
85           current->GetBlock()->RemoveInstruction(current);
86         }
87       }
88     }
89   }
90 }
91 
92 class ArenaPoolAndAllocator {
93  public:
ArenaPoolAndAllocator()94   ArenaPoolAndAllocator()
95       : pool_(), allocator_(&pool_), arena_stack_(&pool_), scoped_allocator_(&arena_stack_) { }
96 
GetAllocator()97   ArenaAllocator* GetAllocator() { return &allocator_; }
GetArenaStack()98   ArenaStack* GetArenaStack() { return &arena_stack_; }
GetScopedAllocator()99   ScopedArenaAllocator* GetScopedAllocator() { return &scoped_allocator_; }
100 
101  private:
102   MallocArenaPool pool_;
103   ArenaAllocator allocator_;
104   ArenaStack arena_stack_;
105   ScopedArenaAllocator scoped_allocator_;
106 };
107 
108 // Have a separate helper so the OptimizingCFITest can inherit it without causing
109 // multiple inheritance errors from having two gtest as a parent twice.
110 class OptimizingUnitTestHelper {
111  public:
OptimizingUnitTestHelper()112   OptimizingUnitTestHelper() : pool_and_allocator_(new ArenaPoolAndAllocator()) { }
113 
GetAllocator()114   ArenaAllocator* GetAllocator() { return pool_and_allocator_->GetAllocator(); }
GetArenaStack()115   ArenaStack* GetArenaStack() { return pool_and_allocator_->GetArenaStack(); }
GetScopedAllocator()116   ScopedArenaAllocator* GetScopedAllocator() { return pool_and_allocator_->GetScopedAllocator(); }
117 
ResetPoolAndAllocator()118   void ResetPoolAndAllocator() {
119     pool_and_allocator_.reset(new ArenaPoolAndAllocator());
120     handles_.reset();  // When getting rid of the old HGraph, we can also reset handles_.
121   }
122 
CreateGraph()123   HGraph* CreateGraph() {
124     ArenaAllocator* const allocator = pool_and_allocator_->GetAllocator();
125 
126     // Reserve a big array of 0s so the dex file constructor can offsets from the header.
127     static constexpr size_t kDexDataSize = 4 * KB;
128     const uint8_t* dex_data = reinterpret_cast<uint8_t*>(allocator->Alloc(kDexDataSize));
129 
130     // Create the dex file based on the fake data. Call the constructor so that we can use virtual
131     // functions. Don't use the arena for the StandardDexFile otherwise the dex location leaks.
132     dex_files_.emplace_back(new StandardDexFile(
133         dex_data,
134         sizeof(StandardDexFile::Header),
135         "no_location",
136         /*location_checksum*/ 0,
137         /*oat_dex_file*/ nullptr,
138         /*container*/ nullptr));
139 
140     return new (allocator) HGraph(
141         allocator,
142         pool_and_allocator_->GetArenaStack(),
143         *dex_files_.back(),
144         /*method_idx*/-1,
145         kRuntimeISA);
146   }
147 
148   // Create a control-flow graph from Dex instructions.
149   HGraph* CreateCFG(const std::vector<uint16_t>& data,
150                     DataType::Type return_type = DataType::Type::kInt32) {
151     HGraph* graph = CreateGraph();
152 
153     // The code item data might not aligned to 4 bytes, copy it to ensure that.
154     const size_t code_item_size = data.size() * sizeof(data.front());
155     void* aligned_data = GetAllocator()->Alloc(code_item_size);
156     memcpy(aligned_data, &data[0], code_item_size);
157     CHECK_ALIGNED(aligned_data, StandardDexFile::CodeItem::kAlignment);
158     const dex::CodeItem* code_item = reinterpret_cast<const dex::CodeItem*>(aligned_data);
159 
160     {
161       ScopedObjectAccess soa(Thread::Current());
162       if (handles_ == nullptr) {
163         handles_.reset(new VariableSizedHandleScope(soa.Self()));
164       }
165       const DexCompilationUnit* dex_compilation_unit =
166           new (graph->GetAllocator()) DexCompilationUnit(
167               handles_->NewHandle<mirror::ClassLoader>(nullptr),
168               /* class_linker= */ nullptr,
169               graph->GetDexFile(),
170               code_item,
171               /* class_def_index= */ DexFile::kDexNoIndex16,
172               /* method_idx= */ dex::kDexNoIndex,
173               /* access_flags= */ 0u,
174               /* verified_method= */ nullptr,
175               handles_->NewHandle<mirror::DexCache>(nullptr));
176       CodeItemDebugInfoAccessor accessor(graph->GetDexFile(), code_item, /*dex_method_idx*/ 0u);
177       HGraphBuilder builder(graph, dex_compilation_unit, accessor, handles_.get(), return_type);
178       bool graph_built = (builder.BuildGraph() == kAnalysisSuccess);
179       return graph_built ? graph : nullptr;
180     }
181   }
182 
183   // Run GraphChecker with all checks.
184   //
185   // Return: the status whether the run is successful.
CheckGraph(HGraph * graph)186   bool CheckGraph(HGraph* graph) {
187     return CheckGraph(graph, /*check_ref_type_info=*/true);
188   }
189 
190   // Run GraphChecker with all checks except reference type information checks.
191   //
192   // Return: the status whether the run is successful.
CheckGraphSkipRefTypeInfoChecks(HGraph * graph)193   bool CheckGraphSkipRefTypeInfoChecks(HGraph* graph) {
194     return CheckGraph(graph, /*check_ref_type_info=*/false);
195   }
196 
197  private:
CheckGraph(HGraph * graph,bool check_ref_type_info)198   bool CheckGraph(HGraph* graph, bool check_ref_type_info) {
199     GraphChecker checker(graph);
200     checker.SetRefTypeInfoCheckEnabled(check_ref_type_info);
201     checker.Run();
202     checker.Dump(std::cerr);
203     return checker.IsValid();
204   }
205 
206   std::vector<std::unique_ptr<const StandardDexFile>> dex_files_;
207   std::unique_ptr<ArenaPoolAndAllocator> pool_and_allocator_;
208   std::unique_ptr<VariableSizedHandleScope> handles_;
209 };
210 
211 class OptimizingUnitTest : public CommonCompilerTest, public OptimizingUnitTestHelper {};
212 
213 // OptimizingUnitTest with some handy functions to ease the graph creation.
214 class ImprovedOptimizingUnitTest : public OptimizingUnitTest {
215  public:
ImprovedOptimizingUnitTest()216   ImprovedOptimizingUnitTest() : graph_(CreateGraph()),
217                                  entry_block_(nullptr),
218                                  return_block_(nullptr),
219                                  exit_block_(nullptr) {}
220 
~ImprovedOptimizingUnitTest()221   virtual ~ImprovedOptimizingUnitTest() {}
222 
InitGraph()223   void InitGraph() {
224     entry_block_ = new (GetAllocator()) HBasicBlock(graph_);
225     graph_->AddBlock(entry_block_);
226     graph_->SetEntryBlock(entry_block_);
227 
228     return_block_ = new (GetAllocator()) HBasicBlock(graph_);
229     graph_->AddBlock(return_block_);
230 
231     exit_block_ = new (GetAllocator()) HBasicBlock(graph_);
232     graph_->AddBlock(exit_block_);
233     graph_->SetExitBlock(exit_block_);
234 
235     entry_block_->AddSuccessor(return_block_);
236     return_block_->AddSuccessor(exit_block_);
237 
238     CreateParameters();
239     for (HInstruction* parameter : parameters_) {
240       entry_block_->AddInstruction(parameter);
241     }
242 
243     return_block_->AddInstruction(new (GetAllocator()) HReturnVoid());
244     exit_block_->AddInstruction(new (GetAllocator()) HExit());
245   }
246 
CheckGraph()247   bool CheckGraph() {
248     return OptimizingUnitTestHelper::CheckGraph(graph_);
249   }
250 
CheckGraphSkipRefTypeInfoChecks()251   bool CheckGraphSkipRefTypeInfoChecks() {
252     return OptimizingUnitTestHelper::CheckGraphSkipRefTypeInfoChecks(graph_);
253   }
254 
ManuallyBuildEnvFor(HInstruction * instruction,ArenaVector<HInstruction * > * current_locals)255   HEnvironment* ManuallyBuildEnvFor(HInstruction* instruction,
256                                     ArenaVector<HInstruction*>* current_locals) {
257     HEnvironment* environment = new (GetAllocator()) HEnvironment(
258         (GetAllocator()),
259         current_locals->size(),
260         graph_->GetArtMethod(),
261         instruction->GetDexPc(),
262         instruction);
263 
264     environment->CopyFrom(ArrayRef<HInstruction* const>(*current_locals));
265     instruction->SetRawEnvironment(environment);
266     return environment;
267   }
268 
269  protected:
270   // Create parameters to be added to the graph entry block.
271   // Subclasses can override it to create parameters they need.
CreateParameters()272   virtual void CreateParameters() { /* do nothing */ }
273 
274   HGraph* graph_;
275 
276   HBasicBlock* entry_block_;
277   HBasicBlock* return_block_;
278   HBasicBlock* exit_block_;
279 
280   std::vector<HInstruction*> parameters_;
281 };
282 
283 // Naive string diff data type.
284 typedef std::list<std::pair<std::string, std::string>> diff_t;
285 
286 // An alias for the empty string used to make it clear that a line is
287 // removed in a diff.
288 static const std::string removed = "";  // NOLINT [runtime/string] [4]
289 
290 // Naive patch command: apply a diff to a string.
Patch(const std::string & original,const diff_t & diff)291 inline std::string Patch(const std::string& original, const diff_t& diff) {
292   std::string result = original;
293   for (const auto& p : diff) {
294     std::string::size_type pos = result.find(p.first);
295     DCHECK_NE(pos, std::string::npos)
296         << "Could not find: \"" << p.first << "\" in \"" << result << "\"";
297     result.replace(pos, p.first.size(), p.second);
298   }
299   return result;
300 }
301 
302 // Returns if the instruction is removed from the graph.
IsRemoved(HInstruction * instruction)303 inline bool IsRemoved(HInstruction* instruction) {
304   return instruction->GetBlock() == nullptr;
305 }
306 
307 }  // namespace art
308 
309 #endif  // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_
310