Home | History | Annotate | Download | only in optimizing 
      1 /*
      2  * Copyright (C) 2017 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 "graph_checker.h"
     18 #include "nodes.h"
     19 #include "optimizing_unit_test.h"
     20 #include "superblock_cloner.h"
     21 
     22 #include "gtest/gtest.h"
     23 
     24 namespace art {
     25 
     26 using HBasicBlockMap = SuperblockCloner::HBasicBlockMap;
     27 using HInstructionMap = SuperblockCloner::HInstructionMap;
     28 
     29 // This class provides methods and helpers for testing various cloning and copying routines:
     30 // individual instruction cloning and cloning of the more coarse-grain structures.
     31 class SuperblockClonerTest : public OptimizingUnitTest {
     32  public:
     33   SuperblockClonerTest()
     34       : graph_(CreateGraph()), entry_block_(nullptr), exit_block_(nullptr), parameter_(nullptr) {}
     35 
     36   void CreateBasicLoopControlFlow(/* out */ HBasicBlock** header_p,
     37                                   /* out */ HBasicBlock** body_p) {
     38     entry_block_ = new (GetAllocator()) HBasicBlock(graph_);
     39     graph_->AddBlock(entry_block_);
     40     graph_->SetEntryBlock(entry_block_);
     41 
     42     HBasicBlock* loop_preheader = new (GetAllocator()) HBasicBlock(graph_);
     43     HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph_);
     44     HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph_);
     45     HBasicBlock* loop_exit = new (GetAllocator()) HBasicBlock(graph_);
     46 
     47     graph_->AddBlock(loop_preheader);
     48     graph_->AddBlock(loop_header);
     49     graph_->AddBlock(loop_body);
     50     graph_->AddBlock(loop_exit);
     51 
     52     exit_block_ = new (GetAllocator()) HBasicBlock(graph_);
     53     graph_->AddBlock(exit_block_);
     54     graph_->SetExitBlock(exit_block_);
     55 
     56     entry_block_->AddSuccessor(loop_preheader);
     57     loop_preheader->AddSuccessor(loop_header);
     58     // Loop exit first to have a proper exit condition/target for HIf.
     59     loop_header->AddSuccessor(loop_exit);
     60     loop_header->AddSuccessor(loop_body);
     61     loop_body->AddSuccessor(loop_header);
     62     loop_exit->AddSuccessor(exit_block_);
     63 
     64     *header_p = loop_header;
     65     *body_p = loop_body;
     66 
     67     parameter_ = new (GetAllocator()) HParameterValue(graph_->GetDexFile(),
     68                                                       dex::TypeIndex(0),
     69                                                       0,
     70                                                       DataType::Type::kInt32);
     71     entry_block_->AddInstruction(parameter_);
     72     loop_exit->AddInstruction(new (GetAllocator()) HReturnVoid());
     73     exit_block_->AddInstruction(new (GetAllocator()) HExit());
     74   }
     75 
     76   void CreateBasicLoopDataFlow(HBasicBlock* loop_header, HBasicBlock* loop_body) {
     77     uint32_t dex_pc = 0;
     78 
     79     // Entry block.
     80     HIntConstant* const_0 = graph_->GetIntConstant(0);
     81     HIntConstant* const_1 = graph_->GetIntConstant(1);
     82     HIntConstant* const_128 = graph_->GetIntConstant(128);
     83 
     84     // Header block.
     85     HPhi* phi = new (GetAllocator()) HPhi(GetAllocator(), 0, 0, DataType::Type::kInt32);
     86     HInstruction* suspend_check = new (GetAllocator()) HSuspendCheck();
     87 
     88     loop_header->AddPhi(phi);
     89     loop_header->AddInstruction(suspend_check);
     90     loop_header->AddInstruction(new (GetAllocator()) HGreaterThanOrEqual(phi, const_128));
     91     loop_header->AddInstruction(new (GetAllocator()) HIf(parameter_));
     92 
     93     // Loop body block.
     94     HInstruction* null_check = new (GetAllocator()) HNullCheck(parameter_, dex_pc);
     95     HInstruction* array_length = new (GetAllocator()) HArrayLength(null_check, dex_pc);
     96     HInstruction* bounds_check = new (GetAllocator()) HBoundsCheck(phi, array_length, dex_pc);
     97     HInstruction* array_get =
     98         new (GetAllocator()) HArrayGet(null_check, bounds_check, DataType::Type::kInt32, dex_pc);
     99     HInstruction* add =  new (GetAllocator()) HAdd(DataType::Type::kInt32, array_get, const_1);
    100     HInstruction* array_set =
    101         new (GetAllocator()) HArraySet(null_check, bounds_check, add, DataType::Type::kInt32, dex_pc);
    102     HInstruction* induction_inc = new (GetAllocator()) HAdd(DataType::Type::kInt32, phi, const_1);
    103 
    104     loop_body->AddInstruction(null_check);
    105     loop_body->AddInstruction(array_length);
    106     loop_body->AddInstruction(bounds_check);
    107     loop_body->AddInstruction(array_get);
    108     loop_body->AddInstruction(add);
    109     loop_body->AddInstruction(array_set);
    110     loop_body->AddInstruction(induction_inc);
    111     loop_body->AddInstruction(new (GetAllocator()) HGoto());
    112 
    113     phi->AddInput(const_0);
    114     phi->AddInput(induction_inc);
    115 
    116     graph_->SetHasBoundsChecks(true);
    117 
    118     // Adjust HEnvironment for each instruction which require that.
    119     ArenaVector<HInstruction*> current_locals({phi, const_128, parameter_},
    120                                               GetAllocator()->Adapter(kArenaAllocInstruction));
    121 
    122     HEnvironment* env = ManuallyBuildEnvFor(suspend_check, &current_locals);
    123     null_check->CopyEnvironmentFrom(env);
    124     bounds_check->CopyEnvironmentFrom(env);
    125   }
    126 
    127   HEnvironment* ManuallyBuildEnvFor(HInstruction* instruction,
    128                                     ArenaVector<HInstruction*>* current_locals) {
    129     HEnvironment* environment = new (GetAllocator()) HEnvironment(
    130         (GetAllocator()),
    131         current_locals->size(),
    132         graph_->GetArtMethod(),
    133         instruction->GetDexPc(),
    134         instruction);
    135 
    136     environment->CopyFrom(ArrayRef<HInstruction* const>(*current_locals));
    137     instruction->SetRawEnvironment(environment);
    138     return environment;
    139   }
    140 
    141   bool CheckGraph() {
    142     GraphChecker checker(graph_);
    143     checker.Run();
    144     if (!checker.IsValid()) {
    145       for (const std::string& error : checker.GetErrors()) {
    146         std::cout << error << std::endl;
    147       }
    148       return false;
    149     }
    150     return true;
    151   }
    152 
    153   HGraph* graph_;
    154 
    155   HBasicBlock* entry_block_;
    156   HBasicBlock* exit_block_;
    157 
    158   HInstruction* parameter_;
    159 };
    160 
    161 TEST_F(SuperblockClonerTest, IndividualInstrCloner) {
    162   HBasicBlock* header = nullptr;
    163   HBasicBlock* loop_body = nullptr;
    164 
    165   CreateBasicLoopControlFlow(&header, &loop_body);
    166   CreateBasicLoopDataFlow(header, loop_body);
    167   graph_->BuildDominatorTree();
    168   ASSERT_TRUE(CheckGraph());
    169 
    170   HSuspendCheck* old_suspend_check = header->GetLoopInformation()->GetSuspendCheck();
    171   CloneAndReplaceInstructionVisitor visitor(graph_);
    172   // Do instruction cloning and replacement twice with different visiting order.
    173 
    174   visitor.VisitInsertionOrder();
    175   size_t instr_replaced_by_clones_count = visitor.GetInstrReplacedByClonesCount();
    176   EXPECT_EQ(instr_replaced_by_clones_count, 12u);
    177   EXPECT_TRUE(CheckGraph());
    178 
    179   visitor.VisitReversePostOrder();
    180   instr_replaced_by_clones_count = visitor.GetInstrReplacedByClonesCount();
    181   EXPECT_EQ(instr_replaced_by_clones_count, 24u);
    182   EXPECT_TRUE(CheckGraph());
    183 
    184   HSuspendCheck* new_suspend_check = header->GetLoopInformation()->GetSuspendCheck();
    185   EXPECT_NE(new_suspend_check, old_suspend_check);
    186   EXPECT_NE(new_suspend_check, nullptr);
    187 }
    188 
    189 // Tests SuperblockCloner::CloneBasicBlocks - check instruction cloning and initial remapping of
    190 // instructions' inputs.
    191 TEST_F(SuperblockClonerTest, CloneBasicBlocks) {
    192   HBasicBlock* header = nullptr;
    193   HBasicBlock* loop_body = nullptr;
    194   ArenaAllocator* arena = graph_->GetAllocator();
    195 
    196   CreateBasicLoopControlFlow(&header, &loop_body);
    197   CreateBasicLoopDataFlow(header, loop_body);
    198   graph_->BuildDominatorTree();
    199   ASSERT_TRUE(CheckGraph());
    200 
    201   ArenaBitVector orig_bb_set(
    202       arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
    203   HBasicBlockMap bb_map(std::less<HBasicBlock*>(), arena->Adapter(kArenaAllocSuperblockCloner));
    204   HInstructionMap hir_map(std::less<HInstruction*>(), arena->Adapter(kArenaAllocSuperblockCloner));
    205 
    206   HLoopInformation* loop_info = header->GetLoopInformation();
    207   orig_bb_set.Union(&loop_info->GetBlocks());
    208 
    209   SuperblockCloner cloner(graph_,
    210                           &orig_bb_set,
    211                           &bb_map,
    212                           &hir_map);
    213   EXPECT_TRUE(cloner.IsSubgraphClonable());
    214 
    215   cloner.CloneBasicBlocks();
    216 
    217   EXPECT_EQ(bb_map.size(), 2u);
    218   EXPECT_EQ(hir_map.size(), 12u);
    219 
    220   for (auto it : hir_map) {
    221     HInstruction* orig_instr = it.first;
    222     HInstruction* copy_instr = it.second;
    223 
    224     EXPECT_EQ(cloner.GetBlockCopy(orig_instr->GetBlock()), copy_instr->GetBlock());
    225     EXPECT_EQ(orig_instr->GetKind(), copy_instr->GetKind());
    226     EXPECT_EQ(orig_instr->GetType(), copy_instr->GetType());
    227 
    228     if (orig_instr->IsPhi()) {
    229       continue;
    230     }
    231 
    232     EXPECT_EQ(orig_instr->InputCount(), copy_instr->InputCount());
    233 
    234     // Check that inputs match.
    235     for (size_t i = 0, e = orig_instr->InputCount(); i < e; i++) {
    236       HInstruction* orig_input = orig_instr->InputAt(i);
    237       HInstruction* copy_input = copy_instr->InputAt(i);
    238       if (cloner.IsInOrigBBSet(orig_input->GetBlock())) {
    239         EXPECT_EQ(cloner.GetInstrCopy(orig_input), copy_input);
    240       } else {
    241         EXPECT_EQ(orig_input, copy_input);
    242       }
    243     }
    244 
    245     EXPECT_EQ(orig_instr->HasEnvironment(), copy_instr->HasEnvironment());
    246 
    247     // Check that environments match.
    248     if (orig_instr->HasEnvironment()) {
    249       HEnvironment* orig_env = orig_instr->GetEnvironment();
    250       HEnvironment* copy_env = copy_instr->GetEnvironment();
    251 
    252       EXPECT_EQ(copy_env->GetParent(), nullptr);
    253       EXPECT_EQ(orig_env->Size(), copy_env->Size());
    254 
    255       for (size_t i = 0, e = orig_env->Size(); i < e; i++) {
    256         HInstruction* orig_input = orig_env->GetInstructionAt(i);
    257         HInstruction* copy_input = copy_env->GetInstructionAt(i);
    258         if (cloner.IsInOrigBBSet(orig_input->GetBlock())) {
    259           EXPECT_EQ(cloner.GetInstrCopy(orig_input), copy_input);
    260         } else {
    261           EXPECT_EQ(orig_input, copy_input);
    262         }
    263       }
    264     }
    265   }
    266 }
    267 
    268 // SuperblockCloner::CleanUpControlFlow - checks algorithms of local adjustments of the control
    269 // flow.
    270 TEST_F(SuperblockClonerTest, AdjustControlFlowInfo) {
    271   HBasicBlock* header = nullptr;
    272   HBasicBlock* loop_body = nullptr;
    273   ArenaAllocator* arena = graph_->GetAllocator();
    274 
    275   CreateBasicLoopControlFlow(&header, &loop_body);
    276   CreateBasicLoopDataFlow(header, loop_body);
    277   graph_->BuildDominatorTree();
    278   ASSERT_TRUE(CheckGraph());
    279 
    280   ArenaBitVector orig_bb_set(
    281       arena, graph_->GetBlocks().size(), false, kArenaAllocSuperblockCloner);
    282 
    283   HLoopInformation* loop_info = header->GetLoopInformation();
    284   orig_bb_set.Union(&loop_info->GetBlocks());
    285 
    286   SuperblockCloner cloner(graph_,
    287                           &orig_bb_set,
    288                           nullptr,
    289                           nullptr);
    290   EXPECT_TRUE(cloner.IsSubgraphClonable());
    291 
    292   cloner.FindAndSetLocalAreaForAdjustments();
    293   cloner.CleanUpControlFlow();
    294 
    295   EXPECT_TRUE(CheckGraph());
    296 
    297   EXPECT_TRUE(entry_block_->Dominates(header));
    298   EXPECT_TRUE(entry_block_->Dominates(exit_block_));
    299 
    300   EXPECT_EQ(header->GetLoopInformation(), loop_info);
    301   EXPECT_EQ(loop_info->GetHeader(), header);
    302   EXPECT_TRUE(loop_info->Contains(*loop_body));
    303   EXPECT_TRUE(loop_info->IsBackEdge(*loop_body));
    304 }
    305 
    306 }  // namespace art
    307