/*
 * 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 "base/arena_allocator.h"
#include "base/macros.h"
#include "builder.h"
#include "code_generator.h"
#include "dex/dex_file.h"
#include "dex/dex_instruction.h"
#include "driver/compiler_options.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
#include "prepare_for_register_allocation.h"
#include "ssa_liveness_analysis.h"

namespace art HIDDEN {

class LiveRangesTest : public CommonCompilerTest, public OptimizingUnitTestHelper {
 protected:
  // Define a shortcut for the `kLivenessPositionsPerInstruction`.
  static constexpr size_t kLppi = kLivenessPositionsPerInstruction;

  HGraph* BuildGraph(const std::vector<uint16_t>& data);

  std::unique_ptr<CompilerOptions> compiler_options_;
};

HGraph* LiveRangesTest::BuildGraph(const std::vector<uint16_t>& data) {
  HGraph* graph = CreateCFG(data);
  compiler_options_ = CommonCompilerTest::CreateCompilerOptions(kRuntimeISA, "default");
  // Suspend checks implementation may change in the future, and this test relies
  // on how instructions are ordered.
  RemoveSuspendChecks(graph);
  // `Inline` conditions into ifs.
  PrepareForRegisterAllocation(graph, *compiler_options_).Run();
  return graph;
}

TEST_F(LiveRangesTest, CFG1) {
  /*
   * Test the following snippet:
   *  return 0;
   *
   * Which becomes the following graph (numbered by lifetime position):
   *       1: constant0
   *       2: goto
   *           |
   *       4: return
   *           |
   *       6: exit
   * (Above positions are multiplied by `kLivenessPositionsPerInstruction`, or `kLppi` for short.)
   */
  const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::RETURN);

  HGraph* graph = BuildGraph(data);

  std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
  SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
  liveness.Analyze();

  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
  LiveRange* range = interval->GetFirstRange();
  ASSERT_EQ(1u * kLppi, range->GetStart());
  // Last use is the return instruction.
  ASSERT_EQ(4u * kLppi, range->GetEnd());
  HBasicBlock* block = graph->GetBlocks()[1];
  ASSERT_TRUE(block->GetLastInstruction()->IsReturn());
  ASSERT_EQ(4u * kLppi, block->GetLastInstruction()->GetLifetimePosition());
  ASSERT_TRUE(range->GetNext() == nullptr);
}

TEST_F(LiveRangesTest, CFG2) {
  /*
   * Test the following snippet:
   *  var a = 0;
   *  if (0 == 0) {
   *  } else {
   *  }
   *  return a;
   *
   * Which becomes the following graph (numbered by lifetime position):
   *       1: constant0
   *       2: goto
   *           |
   *       4: equal
   *       5: if
   *       /       \
   *    7: goto   9: goto
   *       \       /
   *       11: return
   *         |
   *       13: exit
   * (Above positions are multiplied by `kLivenessPositionsPerInstruction`, or `kLppi` for short.)
   */
  const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::IF_EQ, 3,
    Instruction::GOTO | 0x100,
    Instruction::RETURN | 0 << 8);

  HGraph* graph = BuildGraph(data);
  std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
  SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
  liveness.Analyze();

  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
  LiveRange* range = interval->GetFirstRange();
  ASSERT_EQ(1u * kLppi, range->GetStart());
  // Last use is the return instruction.
  ASSERT_EQ(11u * kLppi, range->GetEnd());
  HBasicBlock* block = graph->GetBlocks()[3];
  ASSERT_TRUE(block->GetLastInstruction()->IsReturn());
  ASSERT_EQ(11u * kLppi, block->GetLastInstruction()->GetLifetimePosition());
  ASSERT_TRUE(range->GetNext() == nullptr);
}

TEST_F(LiveRangesTest, CFG3) {
  /*
   * Test the following snippet:
   *  var a = 0;
   *  if (0 == 0) {
   *  } else {
   *    a = 4;
   *  }
   *  return a;
   *
   * Which becomes the following graph (numbered by lifetime position):
   *       1: constant0
   *       2: constant4
   *       3: goto
   *           |
   *       5: equal
   *       6: if
   *       /       \
   *    8: goto   10: goto
   *       \       /
   *       11: phi
   *       12: return
   *         |
   *       14: exit
   * (Above positions are multiplied by `kLivenessPositionsPerInstruction`, or `kLppi` for short.)
   */
  const std::vector<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);

  HGraph* graph = BuildGraph(data);
  std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
  SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
  liveness.Analyze();

  // Test for the 4 constant.
  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
  LiveRange* range = interval->GetFirstRange();
  ASSERT_EQ(2u * kLppi, range->GetStart());
  // Last use is the phi at the return block so instruction is live until
  // the end of the then block.
  ASSERT_EQ(9u * kLppi, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);

  // Test for the 0 constant.
  interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
  // The then branch is a hole for this constant, therefore its interval has 2 ranges.
  // First range starts from the definition and ends at the if block.
  range = interval->GetFirstRange();
  ASSERT_EQ(1u * kLppi, range->GetStart());
  // 14 is the end of the if block.
  ASSERT_EQ(7u * kLppi, range->GetEnd());
  // Second range is the else block.
  range = range->GetNext();
  ASSERT_EQ(9u * kLppi, range->GetStart());
  // Last use is the phi at the return block.
  ASSERT_EQ(11u * kLppi, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);

  // Test for the phi.
  interval = liveness.GetInstructionFromSsaIndex(2)->GetLiveInterval();
  range = interval->GetFirstRange();
  ASSERT_EQ(11u * kLppi, liveness.GetInstructionFromSsaIndex(2)->GetLifetimePosition());
  ASSERT_EQ(11u * kLppi, range->GetStart());
  ASSERT_EQ(12u * kLppi, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);
}

TEST_F(LiveRangesTest, Loop1) {
  /*
   * Test the following snippet:
   *  var a = 0;
   *  while (a == a) {
   *    a = 4;
   *  }
   *  return 5;
   *
   * Which becomes the following graph (numbered by lifetime position):
   *       1: constant0
   *       2: constant5
   *       3: constant4
   *       4: goto
   *           |
   *       6: goto
   *           |
   *       7: phi
   *       8: equal
   *       9: if +++++
   *        |       \ +
   *        |     11: goto
   *        |
   *       13: return
   *         |
   *       15: exit
   * (Above positions are multiplied by `kLivenessPositionsPerInstruction`, or `kLppi` for short.)
   */

  const std::vector<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);

  HGraph* graph = BuildGraph(data);
  RemoveSuspendChecks(graph);
  std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
  SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
  liveness.Analyze();

  // Test for the 0 constant.
  LiveInterval* interval = graph->GetIntConstant(0)->GetLiveInterval();
  LiveRange* range = interval->GetFirstRange();
  ASSERT_EQ(1u * kLppi, range->GetStart());
  // Last use is the loop phi so instruction is live until
  // the end of the pre loop header.
  ASSERT_EQ(7u * kLppi, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);

  // Test for the 4 constant.
  interval = graph->GetIntConstant(4)->GetLiveInterval();
  range = interval->GetFirstRange();
  // The instruction is live until the end of the loop.
  ASSERT_EQ(3u * kLppi, range->GetStart());
  ASSERT_EQ(12u * kLppi, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);

  // Test for the 5 constant.
  interval = graph->GetIntConstant(5)->GetLiveInterval();
  range = interval->GetFirstRange();
  // The instruction is live until the return instruction after the loop.
  ASSERT_EQ(2u * kLppi, range->GetStart());
  ASSERT_EQ(13u * kLppi, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);

  // Test for the phi.
  interval = liveness.GetInstructionFromSsaIndex(3)->GetLiveInterval();
  range = interval->GetFirstRange();
  // Instruction is input of non-materialized Equal and hence live until If.
  ASSERT_EQ(7u * kLppi, range->GetStart());
  ASSERT_EQ(9u * kLppi + kLivenessPositionOfNormalUse, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);
}

TEST_F(LiveRangesTest, Loop2) {
  /*
   * Test the following snippet:
   *  var a = 0;
   *  while (a == a) {
   *    a = a + a;
   *  }
   *  return a;
   *
   * Which becomes the following graph (numbered by lifetime position):
   *       1: constant0
   *       2: goto
   *           |
   *       4: goto
   *           |
   *       5: phi
   *       6: equal
   *       7: if +++++
   *        |       \ +
   *        |     9: add
   *        |     10: goto
   *        |
   *       12: return
   *         |
   *       14: exit
   * We want to make sure the phi at 5 has a lifetime hole after the add at 10.
   * (Above positions are multiplied by `kLivenessPositionsPerInstruction`, or `kLppi` for short.)
   */

  const std::vector<uint16_t> data = ONE_REGISTER_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::IF_EQ, 6,
    Instruction::ADD_INT, 0, 0,
    Instruction::GOTO | 0xFB00,
    Instruction::RETURN | 0 << 8);

  HGraph* graph = BuildGraph(data);
  std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
  SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
  liveness.Analyze();

  // Test for the 0 constant.
  HIntConstant* constant = liveness.GetInstructionFromSsaIndex(0)->AsIntConstant();
  LiveInterval* interval = constant->GetLiveInterval();
  LiveRange* range = interval->GetFirstRange();
  ASSERT_EQ(1u * kLppi, range->GetStart());
  // Last use is the loop phi so instruction is live until
  // the end of the pre loop header.
  ASSERT_EQ(5u * kLppi, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);

  // Test for the loop phi.
  HPhi* phi = liveness.GetInstructionFromSsaIndex(1)->AsPhi();
  interval = phi->GetLiveInterval();
  range = interval->GetFirstRange();
  ASSERT_EQ(5u * kLppi, range->GetStart());
  ASSERT_EQ(9u * kLppi + kLivenessPositionOfNormalUse, range->GetEnd());
  range = range->GetNext();
  ASSERT_TRUE(range != nullptr);
  ASSERT_EQ(11u * kLppi, range->GetStart());
  ASSERT_EQ(12u * kLppi, range->GetEnd());

  // Test for the add instruction.
  HAdd* add = liveness.GetInstructionFromSsaIndex(2)->AsAdd();
  interval = add->GetLiveInterval();
  range = interval->GetFirstRange();
  ASSERT_EQ(36u, range->GetStart());
  ASSERT_EQ(44u, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);
}

TEST_F(LiveRangesTest, CFG4) {
  /*
   * Test the following snippet:
   *  var a = 0;
   *  var b = 4;
   *  if (a == a) {
   *    a = b + a;
   *  } else {
   *    a = b + a
   *  }
   *  return b;
   *
   * Which becomes the following graph (numbered by lifetime position):
   *       1: constant0
   *       2: constant4
   *       3: goto
   *           |
   *       5: equal
   *       6: if
   *       /       \
   *    8: add    11: add
   *    9: goto   12: goto
   *       \       /
   *       13: phi
   *       14: return
   *         |
   *       16: exit
   * We want to make sure the constant0 has a lifetime hole after the 8: add.
   * (Above positions are multiplied by `kLivenessPositionsPerInstruction`, or `kLppi` for short.)
   */
  const std::vector<uint16_t> data = TWO_REGISTERS_CODE_ITEM(
    Instruction::CONST_4 | 0 | 0,
    Instruction::CONST_4 | 4 << 12 | 1 << 8,
    Instruction::IF_EQ, 5,
    Instruction::ADD_INT, 1 << 8,
    Instruction::GOTO | 0x300,
    Instruction::ADD_INT, 1 << 8,
    Instruction::RETURN);

  HGraph* graph = BuildGraph(data);
  std::unique_ptr<CodeGenerator> codegen = CodeGenerator::Create(graph, *compiler_options_);
  SsaLivenessAnalysis liveness(graph, codegen.get(), GetScopedAllocator());
  liveness.Analyze();

  // Test for the 0 constant.
  LiveInterval* interval = liveness.GetInstructionFromSsaIndex(0)->GetLiveInterval();
  LiveRange* range = interval->GetFirstRange();
  ASSERT_EQ(1u * kLppi, range->GetStart());
  ASSERT_EQ(8u * kLppi + kLivenessPositionOfNormalUse, range->GetEnd());
  range = range->GetNext();
  ASSERT_TRUE(range != nullptr);
  ASSERT_EQ(10u * kLppi, range->GetStart());
  ASSERT_EQ(11u * kLppi + kLivenessPositionOfNormalUse, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);

  // Test for the 4 constant.
  interval = liveness.GetInstructionFromSsaIndex(1)->GetLiveInterval();
  range = interval->GetFirstRange();
  ASSERT_EQ(2u * kLppi, range->GetStart());
  ASSERT_EQ(8u * kLppi + kLivenessPositionOfNormalUse, range->GetEnd());
  range = range->GetNext();
  ASSERT_EQ(10u * kLppi, range->GetStart());
  ASSERT_EQ(11u * kLppi + kLivenessPositionOfNormalUse, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);

  // Test for the first add.
  HAdd* add = liveness.GetInstructionFromSsaIndex(2)->AsAdd();
  interval = add->GetLiveInterval();
  range = interval->GetFirstRange();
  ASSERT_EQ(8u * kLppi, range->GetStart());
  ASSERT_EQ(10u * kLppi, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);

  // Test for the second add.
  add = liveness.GetInstructionFromSsaIndex(3)->AsAdd();
  interval = add->GetLiveInterval();
  range = interval->GetFirstRange();
  ASSERT_EQ(11u * kLppi, range->GetStart());
  ASSERT_EQ(13u * kLppi, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);

  HPhi* phi = liveness.GetInstructionFromSsaIndex(4)->AsPhi();
  ASSERT_TRUE(phi->GetUses().HasExactlyOneElement());
  interval = phi->GetLiveInterval();
  range = interval->GetFirstRange();
  ASSERT_EQ(13u * kLppi, range->GetStart());
  ASSERT_EQ(14u * kLppi, range->GetEnd());
  ASSERT_TRUE(range->GetNext() == nullptr);
}

}  // namespace art