compiler/optimizing/liveness_test.cc

/*
 * Copyright (C) 2014 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "builder.h"
#include "dex_file.h"
#include "dex_instruction.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
#include "ssa_liveness_analysis.h"
#include "utils/arena_allocator.h"

#include "gtest/gtest.h"

namespace art {

static void TestCode(const uint16_t* data, const char* expected) {
  ArenaPool pool;
  ArenaAllocator allocator(&pool);
  HGraphBuilder builder(&allocator);
  const DexFile::CodeItem* item = reinterpret_cast<const DexFile::CodeItem*>(data);
  HGraph* graph = builder.BuildGraph(*item);
  ASSERT_NE(graph, nullptr);
  graph->BuildDominatorTree();
  graph->TransformToSSA();
  graph->FindNaturalLoops();
  SsaLivenessAnalysis liveness(*graph);
  liveness.Analyze();

  std::ostringstream buffer;
  for (HInsertionOrderIterator it(*graph); !it.Done(); it.Advance()) {
    HBasicBlock* block = it.Current();
    buffer << "Block " << block->GetBlockId() << std::endl;
    BitVector* live_in = liveness.GetLiveInSet(*block);
    live_in->Dump(buffer, "  live in: ");
    BitVector* live_out = liveness.GetLiveOutSet(*block);
    live_out->Dump(buffer, "  live out: ");
    BitVector* kill = liveness.GetKillSet(*block);
    kill->Dump(buffer, "  kill: ");
  }
  ASSERT_STREQ(expected, buffer.str().c_str());
}

TEST(LivenessTest, CFG1) {
  const char* expected =
    "Block 0\n"
    "  live in: ()\n"
    "  live out: ()\n"
    "  kill: ()\n"
    "Block 1\n"
    "  live in: ()\n"
    "  live out: ()\n"
    "  kill: ()\n"
    "Block 2\n"
    "  live in: ()\n"
    "  live out: ()\n"
    "  kill: ()\n";

  // Constant is not used.
  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::RETURN_VOID);

  TestCode(data, expected);
}

TEST(LivenessTest, CFG2) {
  const char* expected =
    "Block 0\n"
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (10000000000000000000000000000000)\n"
    "  kill: (10000000000000000000000000000000)\n"
    "Block 1\n"
    "  live in: (10000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 2\n"
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n";

  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::RETURN);

  TestCode(data, expected);
}

TEST(LivenessTest, CFG3) {
  const char* expected =
    "Block 0\n"  // entry block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (11000000000000000000000000000000)\n"
    "  kill: (11000000000000000000000000000000)\n"
    "Block 1\n"  // block with add
    "  live in: (11000000000000000000000000000000)\n"
    "  live out: (00100000000000000000000000000000)\n"
    "  kill: (00100000000000000000000000000000)\n"
    "Block 2\n"  // block with return
    "  live in: (00100000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 3\n"  // exit block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n";

  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
    Instruction::CONST_4 | 3 << 12 | 0,
    Instruction::CONST_4 | 4 << 12 | 1 << 8,
    Instruction::ADD_INT_2ADDR | 1 << 12,
    Instruction::GOTO | 0x100,
    Instruction::RETURN);

  TestCode(data, expected);
}

TEST(LivenessTest, CFG4) {
  // var a;
  // if (0 == 0) {
  //   a = 5;
  // } else {
  //   a = 4;
  // }
  // return a;
  //
  // Bitsets are made of:
  // (constant0, constant4, constant5, phi, equal test)
  const char* expected =
    "Block 0\n"  // entry block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (11100000000000000000000000000000)\n"
    "  kill: (11100000000000000000000000000000)\n"
    "Block 1\n"  // block with if
    "  live in: (11100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00010000000000000000000000000000)\n"
    "Block 2\n"  // else block
    "  live in: (01000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 3\n"  // then block
    "  live in: (00100000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 4\n"  // return block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00001000000000000000000000000000)\n"
    "Block 5\n"  // exit block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n";

  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::IF_EQ, 4,
    Instruction::CONST_4 | 4 << 12 | 0,
    Instruction::GOTO | 0x200,
    Instruction::CONST_4 | 5 << 12 | 0,
    Instruction::RETURN | 0 << 8);

  TestCode(data, expected);
}

TEST(LivenessTest, CFG5) {
  // var a = 0;
  // if (0 == 0) {
  // } else {
  //   a = 4;
  // }
  // return a;
  const char* expected =
    "Block 0\n"  // entry block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (11000000000000000000000000000000)\n"
    "  kill: (11000000000000000000000000000000)\n"
    "Block 1\n"  // block with if
    "  live in: (11000000000000000000000000000000)\n"
    "  live out: (11000000000000000000000000000000)\n"
    "  kill: (00100000000000000000000000000000)\n"
    "Block 2\n"  // else block
    "  live in: (01000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 3\n"  // return block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00010000000000000000000000000000)\n"
    "Block 4\n"  // exit block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 5\n"  // block to avoid critical edge. Predecessor is 1, successor is 3.
    "  live in: (10000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n";

  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::IF_EQ, 3,
    Instruction::CONST_4 | 4 << 12 | 0,
    Instruction::RETURN | 0 << 8);

  TestCode(data, expected);
}

TEST(LivenessTest, Loop1) {
  // Simple loop with one preheader and one back edge.
  // var a = 0;
  // while (a == a) {
  //   a = 4;
  // }
  // return;
  const char* expected =
    "Block 0\n"  // entry block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (11000000000000000000000000000000)\n"
    "  kill: (11000000000000000000000000000000)\n"
    "Block 1\n"  // pre header
    "  live in: (11000000000000000000000000000000)\n"
    "  live out: (01000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 2\n"  // loop header
    "  live in: (01000000000000000000000000000000)\n"
    "  live out: (01000000000000000000000000000000)\n"
    "  kill: (00110000000000000000000000000000)\n"
    "Block 3\n"  // back edge
    "  live in: (01000000000000000000000000000000)\n"
    "  live out: (01000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 4\n"  // return block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 5\n"  // exit block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n";


  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::IF_EQ, 4,
    Instruction::CONST_4 | 4 << 12 | 0,
    Instruction::GOTO | 0xFD00,
    Instruction::RETURN_VOID);

  TestCode(data, expected);
}

TEST(LivenessTest, Loop3) {
  // Test that the returned value stays live in a preceding loop.
  // var a = 0;
  // while (a == a) {
  //   a = 4;
  // }
  // return 5;
  const char* expected =
    "Block 0\n"
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (11100000000000000000000000000000)\n"
    "  kill: (11100000000000000000000000000000)\n"
    "Block 1\n"
    "  live in: (11100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 2\n"  // loop header
    "  live in: (01100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00011000000000000000000000000000)\n"
    "Block 3\n"  // back edge
    "  live in: (01100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 4\n"  // return block
    "  live in: (00100000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 5\n"  // exit block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n";

  const uint16_t data[] = TWO_REGISTERS_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::IF_EQ, 4,
    Instruction::CONST_4 | 4 << 12 | 0,
    Instruction::GOTO | 0xFD00,
    Instruction::CONST_4 | 5 << 12 | 1 << 8,
    Instruction::RETURN | 1 << 8);

  TestCode(data, expected);
}


TEST(LivenessTest, Loop4) {
  // Make sure we support a preheader of a loop not being the first predecessor
  // in the predecessor list of the header.
  // var a = 0;
  // while (a == a) {
  //   a = 4;
  // }
  // return a;
  // Bitsets are made of:
  // (constant0, constant4, phi, equal test)
  const char* expected =
    "Block 0\n"
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (11000000000000000000000000000000)\n"
    "  kill: (11000000000000000000000000000000)\n"
    "Block 1\n"
    "  live in: (11000000000000000000000000000000)\n"
    "  live out: (11000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 2\n"  // loop header
    "  live in: (01000000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00110000000000000000000000000000)\n"
    "Block 3\n"  // back edge
    "  live in: (01000000000000000000000000000000)\n"
    "  live out: (01000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 4\n"  // pre loop header
    "  live in: (11000000000000000000000000000000)\n"
    "  live out: (01000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 5\n"  // return block
    "  live in: (00100000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 6\n"  // exit block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n";

  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::GOTO | 0x500,
    Instruction::IF_EQ, 5,
    Instruction::CONST_4 | 4 << 12 | 0,
    Instruction::GOTO | 0xFD00,
    Instruction::GOTO | 0xFC00,
    Instruction::RETURN | 0 << 8);

  TestCode(data, expected);
}

TEST(LivenessTest, Loop5) {
  // Make sure we create a preheader of a loop when a header originally has two
  // incoming blocks and one back edge.
  // Bitsets are made of:
  // (constant0, constant4, constant5, equal in block 1, phi in block 8, phi in block 4,
  //  equal in block 4)
  const char* expected =
    "Block 0\n"
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (11100000000000000000000000000000)\n"
    "  kill: (11100000000000000000000000000000)\n"
    "Block 1\n"
    "  live in: (11100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00010000000000000000000000000000)\n"
    "Block 2\n"
    "  live in: (01000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 3\n"
    "  live in: (00100000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 4\n"  // loop header
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000100000000000000000000000000)\n"
    "  kill: (00000110000000000000000000000000)\n"
    "Block 5\n"  // back edge
    "  live in: (00000100000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 6\n"  // return block
    "  live in: (00000100000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 7\n"  // exit block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 8\n"  // synthesized pre header
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00001000000000000000000000000000)\n";

  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::IF_EQ, 4,
    Instruction::CONST_4 | 4 << 12 | 0,
    Instruction::GOTO | 0x200,
    Instruction::CONST_4 | 5 << 12 | 0,
    Instruction::IF_EQ, 3,
    Instruction::GOTO | 0xFE00,
    Instruction::RETURN | 0 << 8);

  TestCode(data, expected);
}

TEST(LivenessTest, Loop6) {
  // Bitsets are made of:
  // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3,
  //  phi in block 8)
  const char* expected =
    "Block 0\n"
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (11100000000000000000000000000000)\n"
    "  kill: (11100000000000000000000000000000)\n"
    "Block 1\n"
    "  live in: (11100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 2\n"  // loop header
    "  live in: (01100000000000000000000000000000)\n"
    "  live out: (01110000000000000000000000000000)\n"
    "  kill: (00011000000000000000000000000000)\n"
    "Block 3\n"
    "  live in: (01100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00000100000000000000000000000000)\n"
    "Block 4\n"  // original back edge
    "  live in: (01100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 5\n"  // original back edge
    "  live in: (01100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 6\n"  // return block
    "  live in: (00010000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 7\n"  // exit block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 8\n"  // synthesized back edge
    "  live in: (01100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00000010000000000000000000000000)\n";

  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::IF_EQ, 8,
    Instruction::CONST_4 | 4 << 12 | 0,
    Instruction::IF_EQ, 4,
    Instruction::CONST_4 | 5 << 12 | 0,
    Instruction::GOTO | 0xFA00,
    Instruction::GOTO | 0xF900,
    Instruction::RETURN | 0 << 8);

  TestCode(data, expected);
}


TEST(LivenessTest, Loop7) {
  // Bitsets are made of:
  // (constant0, constant4, constant5, phi in block 2, equal in block 2, equal in block 3,
  //  phi in block 6)
  const char* expected =
    "Block 0\n"
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (11100000000000000000000000000000)\n"
    "  kill: (11100000000000000000000000000000)\n"
    "Block 1\n"
    "  live in: (11100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 2\n"  // loop header
    "  live in: (01100000000000000000000000000000)\n"
    "  live out: (01110000000000000000000000000000)\n"
    "  kill: (00011000000000000000000000000000)\n"
    "Block 3\n"
    "  live in: (01100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00000100000000000000000000000000)\n"
    "Block 4\n"  // loop exit
    "  live in: (00100000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 5\n"  // back edge
    "  live in: (01100000000000000000000000000000)\n"
    "  live out: (01100000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 6\n"  // return block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000010000000000000000000000000)\n"
    "Block 7\n"  // exit block
    "  live in: (00000000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n"
    "Block 8\n"  // synthesized block to avoid critical edge.
    "  live in: (00010000000000000000000000000000)\n"
    "  live out: (00000000000000000000000000000000)\n"
    "  kill: (00000000000000000000000000000000)\n";

  const uint16_t data[] = ONE_REGISTER_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::IF_EQ, 8,
    Instruction::CONST_4 | 4 << 12 | 0,
    Instruction::IF_EQ, 4,
    Instruction::CONST_4 | 5 << 12 | 0,
    Instruction::GOTO | 0x0200,
    Instruction::GOTO | 0xF900,
    Instruction::RETURN | 0 << 8);

  TestCode(data, expected);
}

}  // namespace art