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 #include "graph_checker.h"
     18 #include "optimizing_unit_test.h"
     19 
     20 namespace art {
     21 
     22 class GraphCheckerTest : public OptimizingUnitTest {
     23  protected:
     24   HGraph* CreateSimpleCFG();
     25   void TestCode(const std::vector<uint16_t>& data);
     26 };
     27 
     28 /**
     29  * Create a simple control-flow graph composed of two blocks:
     30  *
     31  *   BasicBlock 0, succ: 1
     32  *     0: ReturnVoid 1
     33  *   BasicBlock 1, pred: 0
     34  *     1: Exit
     35  */
     36 HGraph* GraphCheckerTest::CreateSimpleCFG() {
     37   HGraph* graph = CreateGraph();
     38   HBasicBlock* entry_block = new (GetAllocator()) HBasicBlock(graph);
     39   entry_block->AddInstruction(new (GetAllocator()) HReturnVoid());
     40   graph->AddBlock(entry_block);
     41   graph->SetEntryBlock(entry_block);
     42   HBasicBlock* exit_block = new (GetAllocator()) HBasicBlock(graph);
     43   exit_block->AddInstruction(new (GetAllocator()) HExit());
     44   graph->AddBlock(exit_block);
     45   graph->SetExitBlock(exit_block);
     46   entry_block->AddSuccessor(exit_block);
     47   graph->BuildDominatorTree();
     48   return graph;
     49 }
     50 
     51 void GraphCheckerTest::TestCode(const std::vector<uint16_t>& data) {
     52   HGraph* graph = CreateCFG(data);
     53   ASSERT_NE(graph, nullptr);
     54 
     55   GraphChecker graph_checker(graph);
     56   graph_checker.Run();
     57   ASSERT_TRUE(graph_checker.IsValid());
     58 }
     59 
     60 TEST_F(GraphCheckerTest, ReturnVoid) {
     61   const std::vector<uint16_t> data = ZERO_REGISTER_CODE_ITEM(
     62       Instruction::RETURN_VOID);
     63 
     64   TestCode(data);
     65 }
     66 
     67 TEST_F(GraphCheckerTest, CFG1) {
     68   const std::vector<uint16_t> data = ZERO_REGISTER_CODE_ITEM(
     69       Instruction::GOTO | 0x100,
     70       Instruction::RETURN_VOID);
     71 
     72   TestCode(data);
     73 }
     74 
     75 TEST_F(GraphCheckerTest, CFG2) {
     76   const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
     77     Instruction::CONST_4 | 0 | 0,
     78     Instruction::IF_EQ, 3,
     79     Instruction::GOTO | 0x100,
     80     Instruction::RETURN_VOID);
     81 
     82   TestCode(data);
     83 }
     84 
     85 TEST_F(GraphCheckerTest, CFG3) {
     86   const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
     87     Instruction::CONST_4 | 0 | 0,
     88     Instruction::IF_EQ, 3,
     89     Instruction::GOTO | 0x100,
     90     Instruction::GOTO | 0xFF00);
     91 
     92   TestCode(data);
     93 }
     94 
     95 // Test case with an invalid graph containing inconsistent
     96 // predecessor/successor arcs in CFG.
     97 TEST_F(GraphCheckerTest, InconsistentPredecessorsAndSuccessors) {
     98   HGraph* graph = CreateSimpleCFG();
     99   GraphChecker graph_checker(graph);
    100   graph_checker.Run();
    101   ASSERT_TRUE(graph_checker.IsValid());
    102 
    103   // Remove the entry block from the exit block's predecessors, to create an
    104   // inconsistent successor/predecessor relation.
    105   graph->GetExitBlock()->RemovePredecessor(graph->GetEntryBlock());
    106   graph_checker.Run();
    107   ASSERT_FALSE(graph_checker.IsValid());
    108 }
    109 
    110 // Test case with an invalid graph containing a non-branch last
    111 // instruction in a block.
    112 TEST_F(GraphCheckerTest, BlockEndingWithNonBranchInstruction) {
    113   HGraph* graph = CreateSimpleCFG();
    114   GraphChecker graph_checker(graph);
    115   graph_checker.Run();
    116   ASSERT_TRUE(graph_checker.IsValid());
    117 
    118   // Remove the sole instruction of the exit block (composed of a
    119   // single Exit instruction) to make it invalid (i.e. not ending by a
    120   // branch instruction).
    121   HBasicBlock* exit_block = graph->GetExitBlock();
    122   HInstruction* last_inst = exit_block->GetLastInstruction();
    123   exit_block->RemoveInstruction(last_inst);
    124 
    125   graph_checker.Run();
    126   ASSERT_FALSE(graph_checker.IsValid());
    127 }
    128 
    129 TEST_F(GraphCheckerTest, SSAPhi) {
    130   // This code creates one Phi function during the conversion to SSA form.
    131   const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
    132     Instruction::CONST_4 | 0 | 0,
    133     Instruction::IF_EQ, 3,
    134     Instruction::CONST_4 | 4 << 12 | 0,
    135     Instruction::RETURN | 0 << 8);
    136 
    137   TestCode(data);
    138 }
    139 
    140 }  // namespace art
    141