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