Home | History | Annotate | Download | only in optimizing 
      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 
     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:
     94   ArenaPoolAndAllocator()
     95       : pool_(), allocator_(&pool_), arena_stack_(&pool_), scoped_allocator_(&arena_stack_) { }
     96 
     97   ArenaAllocator* GetAllocator() { return &allocator_; }
     98   ArenaStack* GetArenaStack() { return &arena_stack_; }
     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:
    112   OptimizingUnitTestHelper() : pool_and_allocator_(new ArenaPoolAndAllocator()) { }
    113 
    114   ArenaAllocator* GetAllocator() { return pool_and_allocator_->GetAllocator(); }
    115   ArenaStack* GetArenaStack() { return pool_and_allocator_->GetArenaStack(); }
    116   ScopedArenaAllocator* GetScopedAllocator() { return pool_and_allocator_->GetScopedAllocator(); }
    117 
    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 
    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  private:
    184   std::vector<std::unique_ptr<const StandardDexFile>> dex_files_;
    185   std::unique_ptr<ArenaPoolAndAllocator> pool_and_allocator_;
    186   std::unique_ptr<VariableSizedHandleScope> handles_;
    187 };
    188 
    189 class OptimizingUnitTest : public CommonCompilerTest, public OptimizingUnitTestHelper {};
    190 
    191 // OptimizingUnitTest with some handy functions to ease the graph creation.
    192 class ImprovedOptimizingUnitTest : public OptimizingUnitTest {
    193  public:
    194   ImprovedOptimizingUnitTest() : graph_(CreateGraph()),
    195                                  entry_block_(nullptr),
    196                                  return_block_(nullptr),
    197                                  exit_block_(nullptr),
    198                                  parameter_(nullptr) {}
    199 
    200   virtual ~ImprovedOptimizingUnitTest() {}
    201 
    202   void InitGraph() {
    203     entry_block_ = new (GetAllocator()) HBasicBlock(graph_);
    204     graph_->AddBlock(entry_block_);
    205     graph_->SetEntryBlock(entry_block_);
    206 
    207     return_block_ = new (GetAllocator()) HBasicBlock(graph_);
    208     graph_->AddBlock(return_block_);
    209 
    210     exit_block_ = new (GetAllocator()) HBasicBlock(graph_);
    211     graph_->AddBlock(exit_block_);
    212     graph_->SetExitBlock(exit_block_);
    213 
    214     entry_block_->AddSuccessor(return_block_);
    215     return_block_->AddSuccessor(exit_block_);
    216 
    217     parameter_ = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
    218                                                       dex::TypeIndex(0),
    219                                                       0,
    220                                                       DataType::Type::kInt32);
    221     entry_block_->AddInstruction(parameter_);
    222     return_block_->AddInstruction(new (GetAllocator()) HReturnVoid());
    223     exit_block_->AddInstruction(new (GetAllocator()) HExit());
    224   }
    225 
    226   bool CheckGraph() {
    227     GraphChecker checker(graph_);
    228     checker.Run();
    229     if (!checker.IsValid()) {
    230       for (const std::string& error : checker.GetErrors()) {
    231         std::cout << error << std::endl;
    232       }
    233       return false;
    234     }
    235     return true;
    236   }
    237 
    238   HEnvironment* ManuallyBuildEnvFor(HInstruction* instruction,
    239                                     ArenaVector<HInstruction*>* current_locals) {
    240     HEnvironment* environment = new (GetAllocator()) HEnvironment(
    241         (GetAllocator()),
    242         current_locals->size(),
    243         graph_->GetArtMethod(),
    244         instruction->GetDexPc(),
    245         instruction);
    246 
    247     environment->CopyFrom(ArrayRef<HInstruction* const>(*current_locals));
    248     instruction->SetRawEnvironment(environment);
    249     return environment;
    250   }
    251 
    252  protected:
    253   HGraph* graph_;
    254 
    255   HBasicBlock* entry_block_;
    256   HBasicBlock* return_block_;
    257   HBasicBlock* exit_block_;
    258 
    259   HInstruction* parameter_;
    260 };
    261 
    262 // Naive string diff data type.
    263 typedef std::list<std::pair<std::string, std::string>> diff_t;
    264 
    265 // An alias for the empty string used to make it clear that a line is
    266 // removed in a diff.
    267 static const std::string removed = "";  // NOLINT [runtime/string] [4]
    268 
    269 // Naive patch command: apply a diff to a string.
    270 inline std::string Patch(const std::string& original, const diff_t& diff) {
    271   std::string result = original;
    272   for (const auto& p : diff) {
    273     std::string::size_type pos = result.find(p.first);
    274     DCHECK_NE(pos, std::string::npos)
    275         << "Could not find: \"" << p.first << "\" in \"" << result << "\"";
    276     result.replace(pos, p.first.size(), p.second);
    277   }
    278   return result;
    279 }
    280 
    281 // Returns if the instruction is removed from the graph.
    282 inline bool IsRemoved(HInstruction* instruction) {
    283   return instruction->GetBlock() == nullptr;
    284 }
    285 
    286 }  // namespace art
    287 
    288 #endif  // ART_COMPILER_OPTIMIZING_OPTIMIZING_UNIT_TEST_H_
    289