/*
 * 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 "gvn.h"

#include "base/arena_allocator.h"
#include "builder.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
#include "side_effects_analysis.h"

namespace art {

class GVNTest : public OptimizingUnitTest {};

TEST_F(GVNTest, LocalFieldElimination) {
  HGraph* graph = CreateGraph();
  HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
  graph->AddBlock(entry);
  graph->SetEntryBlock(entry);
  HInstruction* parameter = new (GetAllocator()) HParameterValue(graph->GetDexFile(),
                                                                 dex::TypeIndex(0),
                                                                 0,
                                                                 DataType::Type::kReference);
  entry->AddInstruction(parameter);

  HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
  graph->AddBlock(block);
  entry->AddSuccessor(block);

  block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
                                                               nullptr,
                                                               DataType::Type::kReference,
                                                               MemberOffset(42),
                                                               false,
                                                               kUnknownFieldIndex,
                                                               kUnknownClassDefIndex,
                                                               graph->GetDexFile(),
                                                               0));
  block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
                                                               nullptr,
                                                               DataType::Type::kReference,
                                                               MemberOffset(42),
                                                               false,
                                                               kUnknownFieldIndex,
                                                               kUnknownClassDefIndex,
                                                               graph->GetDexFile(),
                                                               0));
  HInstruction* to_remove = block->GetLastInstruction();
  block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
                                                               nullptr,
                                                               DataType::Type::kReference,
                                                               MemberOffset(43),
                                                               false,
                                                               kUnknownFieldIndex,
                                                               kUnknownClassDefIndex,
                                                               graph->GetDexFile(),
                                                               0));
  HInstruction* different_offset = block->GetLastInstruction();
  // Kill the value.
  block->AddInstruction(new (GetAllocator()) HInstanceFieldSet(parameter,
                                                               parameter,
                                                               nullptr,
                                                               DataType::Type::kReference,
                                                               MemberOffset(42),
                                                               false,
                                                               kUnknownFieldIndex,
                                                               kUnknownClassDefIndex,
                                                               graph->GetDexFile(),
                                                               0));
  block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
                                                               nullptr,
                                                               DataType::Type::kReference,
                                                               MemberOffset(42),
                                                               false,
                                                               kUnknownFieldIndex,
                                                               kUnknownClassDefIndex,
                                                               graph->GetDexFile(),
                                                               0));
  HInstruction* use_after_kill = block->GetLastInstruction();
  block->AddInstruction(new (GetAllocator()) HExit());

  ASSERT_EQ(to_remove->GetBlock(), block);
  ASSERT_EQ(different_offset->GetBlock(), block);
  ASSERT_EQ(use_after_kill->GetBlock(), block);

  graph->BuildDominatorTree();
  SideEffectsAnalysis side_effects(graph);
  side_effects.Run();
  GVNOptimization(graph, side_effects).Run();

  ASSERT_TRUE(to_remove->GetBlock() == nullptr);
  ASSERT_EQ(different_offset->GetBlock(), block);
  ASSERT_EQ(use_after_kill->GetBlock(), block);
}

TEST_F(GVNTest, GlobalFieldElimination) {
  HGraph* graph = CreateGraph();
  HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
  graph->AddBlock(entry);
  graph->SetEntryBlock(entry);
  HInstruction* parameter = new (GetAllocator()) HParameterValue(graph->GetDexFile(),
                                                                 dex::TypeIndex(0),
                                                                 0,
                                                                 DataType::Type::kReference);
  entry->AddInstruction(parameter);

  HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
  graph->AddBlock(block);
  entry->AddSuccessor(block);
  block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
                                                               nullptr,
                                                               DataType::Type::kBool,
                                                               MemberOffset(42),
                                                               false,
                                                               kUnknownFieldIndex,
                                                               kUnknownClassDefIndex,
                                                               graph->GetDexFile(),
                                                               0));

  block->AddInstruction(new (GetAllocator()) HIf(block->GetLastInstruction()));
  HBasicBlock* then = new (GetAllocator()) HBasicBlock(graph);
  HBasicBlock* else_ = new (GetAllocator()) HBasicBlock(graph);
  HBasicBlock* join = new (GetAllocator()) HBasicBlock(graph);
  graph->AddBlock(then);
  graph->AddBlock(else_);
  graph->AddBlock(join);

  block->AddSuccessor(then);
  block->AddSuccessor(else_);
  then->AddSuccessor(join);
  else_->AddSuccessor(join);

  then->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
                                                              nullptr,
                                                              DataType::Type::kBool,
                                                              MemberOffset(42),
                                                              false,
                                                              kUnknownFieldIndex,
                                                              kUnknownClassDefIndex,
                                                              graph->GetDexFile(),
                                                              0));
  then->AddInstruction(new (GetAllocator()) HGoto());
  else_->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
                                                               nullptr,
                                                               DataType::Type::kBool,
                                                               MemberOffset(42),
                                                               false,
                                                               kUnknownFieldIndex,
                                                               kUnknownClassDefIndex,
                                                               graph->GetDexFile(),
                                                               0));
  else_->AddInstruction(new (GetAllocator()) HGoto());
  join->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
                                                              nullptr,
                                                              DataType::Type::kBool,
                                                              MemberOffset(42),
                                                              false,
                                                              kUnknownFieldIndex,
                                                              kUnknownClassDefIndex,
                                                              graph->GetDexFile(),
                                                              0));
  join->AddInstruction(new (GetAllocator()) HExit());

  graph->BuildDominatorTree();
  SideEffectsAnalysis side_effects(graph);
  side_effects.Run();
  GVNOptimization(graph, side_effects).Run();

  // Check that all field get instructions have been GVN'ed.
  ASSERT_TRUE(then->GetFirstInstruction()->IsGoto());
  ASSERT_TRUE(else_->GetFirstInstruction()->IsGoto());
  ASSERT_TRUE(join->GetFirstInstruction()->IsExit());
}

TEST_F(GVNTest, LoopFieldElimination) {
  HGraph* graph = CreateGraph();
  HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
  graph->AddBlock(entry);
  graph->SetEntryBlock(entry);

  HInstruction* parameter = new (GetAllocator()) HParameterValue(graph->GetDexFile(),
                                                                 dex::TypeIndex(0),
                                                                 0,
                                                                 DataType::Type::kReference);
  entry->AddInstruction(parameter);

  HBasicBlock* block = new (GetAllocator()) HBasicBlock(graph);
  graph->AddBlock(block);
  entry->AddSuccessor(block);
  block->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
                                                               nullptr,
                                                               DataType::Type::kBool,
                                                               MemberOffset(42),
                                                               false,
                                                               kUnknownFieldIndex,
                                                               kUnknownClassDefIndex,
                                                               graph->GetDexFile(),
                                                               0));
  block->AddInstruction(new (GetAllocator()) HGoto());

  HBasicBlock* loop_header = new (GetAllocator()) HBasicBlock(graph);
  HBasicBlock* loop_body = new (GetAllocator()) HBasicBlock(graph);
  HBasicBlock* exit = new (GetAllocator()) HBasicBlock(graph);

  graph->AddBlock(loop_header);
  graph->AddBlock(loop_body);
  graph->AddBlock(exit);
  block->AddSuccessor(loop_header);
  loop_header->AddSuccessor(loop_body);
  loop_header->AddSuccessor(exit);
  loop_body->AddSuccessor(loop_header);

  loop_header->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
                                                                     nullptr,
                                                                     DataType::Type::kBool,
                                                                     MemberOffset(42),
                                                                     false,
                                                                     kUnknownFieldIndex,
                                                                     kUnknownClassDefIndex,
                                                                     graph->GetDexFile(),
                                                                     0));
  HInstruction* field_get_in_loop_header = loop_header->GetLastInstruction();
  loop_header->AddInstruction(new (GetAllocator()) HIf(block->GetLastInstruction()));

  // Kill inside the loop body to prevent field gets inside the loop header
  // and the body to be GVN'ed.
  loop_body->AddInstruction(new (GetAllocator()) HInstanceFieldSet(parameter,
                                                                   parameter,
                                                                   nullptr,
                                                                   DataType::Type::kBool,
                                                                   MemberOffset(42),
                                                                   false,
                                                                   kUnknownFieldIndex,
                                                                   kUnknownClassDefIndex,
                                                                   graph->GetDexFile(),
                                                                   0));
  HInstruction* field_set = loop_body->GetLastInstruction();
  loop_body->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
                                                                   nullptr,
                                                                   DataType::Type::kBool,
                                                                   MemberOffset(42),
                                                                   false,
                                                                   kUnknownFieldIndex,
                                                                   kUnknownClassDefIndex,
                                                                   graph->GetDexFile(),
                                                                   0));
  HInstruction* field_get_in_loop_body = loop_body->GetLastInstruction();
  loop_body->AddInstruction(new (GetAllocator()) HGoto());

  exit->AddInstruction(new (GetAllocator()) HInstanceFieldGet(parameter,
                                                              nullptr,
                                                              DataType::Type::kBool,
                                                              MemberOffset(42),
                                                              false,
                                                              kUnknownFieldIndex,
                                                              kUnknownClassDefIndex,
                                                              graph->GetDexFile(),
                                                              0));
  HInstruction* field_get_in_exit = exit->GetLastInstruction();
  exit->AddInstruction(new (GetAllocator()) HExit());

  ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
  ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
  ASSERT_EQ(field_get_in_exit->GetBlock(), exit);

  graph->BuildDominatorTree();
  {
    SideEffectsAnalysis side_effects(graph);
    side_effects.Run();
    GVNOptimization(graph, side_effects).Run();
  }

  // Check that all field get instructions are still there.
  ASSERT_EQ(field_get_in_loop_header->GetBlock(), loop_header);
  ASSERT_EQ(field_get_in_loop_body->GetBlock(), loop_body);
  // The exit block is dominated by the loop header, whose field get
  // does not get killed by the loop flags.
  ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr);

  // Now remove the field set, and check that all field get instructions have been GVN'ed.
  loop_body->RemoveInstruction(field_set);
  {
    SideEffectsAnalysis side_effects(graph);
    side_effects.Run();
    GVNOptimization(graph, side_effects).Run();
  }

  ASSERT_TRUE(field_get_in_loop_header->GetBlock() == nullptr);
  ASSERT_TRUE(field_get_in_loop_body->GetBlock() == nullptr);
  ASSERT_TRUE(field_get_in_exit->GetBlock() == nullptr);
}

// Test that inner loops affect the side effects of the outer loop.
TEST_F(GVNTest, LoopSideEffects) {
  static const SideEffects kCanTriggerGC = SideEffects::CanTriggerGC();

  HGraph* graph = CreateGraph();
  HBasicBlock* entry = new (GetAllocator()) HBasicBlock(graph);
  graph->AddBlock(entry);
  graph->SetEntryBlock(entry);

  HBasicBlock* outer_loop_header = new (GetAllocator()) HBasicBlock(graph);
  HBasicBlock* outer_loop_body = new (GetAllocator()) HBasicBlock(graph);
  HBasicBlock* outer_loop_exit = new (GetAllocator()) HBasicBlock(graph);
  HBasicBlock* inner_loop_header = new (GetAllocator()) HBasicBlock(graph);
  HBasicBlock* inner_loop_body = new (GetAllocator()) HBasicBlock(graph);
  HBasicBlock* inner_loop_exit = new (GetAllocator()) HBasicBlock(graph);

  graph->AddBlock(outer_loop_header);
  graph->AddBlock(outer_loop_body);
  graph->AddBlock(outer_loop_exit);
  graph->AddBlock(inner_loop_header);
  graph->AddBlock(inner_loop_body);
  graph->AddBlock(inner_loop_exit);

  entry->AddSuccessor(outer_loop_header);
  outer_loop_header->AddSuccessor(outer_loop_body);
  outer_loop_header->AddSuccessor(outer_loop_exit);
  outer_loop_body->AddSuccessor(inner_loop_header);
  inner_loop_header->AddSuccessor(inner_loop_body);
  inner_loop_header->AddSuccessor(inner_loop_exit);
  inner_loop_body->AddSuccessor(inner_loop_header);
  inner_loop_exit->AddSuccessor(outer_loop_header);

  HInstruction* parameter = new (GetAllocator()) HParameterValue(graph->GetDexFile(),
                                                                 dex::TypeIndex(0),
                                                                 0,
                                                                 DataType::Type::kBool);
  entry->AddInstruction(parameter);
  entry->AddInstruction(new (GetAllocator()) HGoto());
  outer_loop_header->AddInstruction(new (GetAllocator()) HSuspendCheck());
  outer_loop_header->AddInstruction(new (GetAllocator()) HIf(parameter));
  outer_loop_body->AddInstruction(new (GetAllocator()) HGoto());
  inner_loop_header->AddInstruction(new (GetAllocator()) HSuspendCheck());
  inner_loop_header->AddInstruction(new (GetAllocator()) HIf(parameter));
  inner_loop_body->AddInstruction(new (GetAllocator()) HGoto());
  inner_loop_exit->AddInstruction(new (GetAllocator()) HGoto());
  outer_loop_exit->AddInstruction(new (GetAllocator()) HExit());

  graph->BuildDominatorTree();

  ASSERT_TRUE(inner_loop_header->GetLoopInformation()->IsIn(
      *outer_loop_header->GetLoopInformation()));

  // Check that the only side effect of loops is to potentially trigger GC.
  {
    // Make one block with a side effect.
    entry->AddInstruction(new (GetAllocator()) HInstanceFieldSet(parameter,
                                                                 parameter,
                                                                 nullptr,
                                                                 DataType::Type::kReference,
                                                                 MemberOffset(42),
                                                                 false,
                                                                 kUnknownFieldIndex,
                                                                 kUnknownClassDefIndex,
                                                                 graph->GetDexFile(),
                                                                 0));

    SideEffectsAnalysis side_effects(graph);
    side_effects.Run();

    ASSERT_TRUE(side_effects.GetBlockEffects(entry).DoesAnyWrite());
    ASSERT_FALSE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite());
    ASSERT_FALSE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite());
    ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite());
    ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).Equals(kCanTriggerGC));
    ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).Equals(kCanTriggerGC));
  }

  // Check that the side effects of the outer loop does not affect the inner loop.
  {
    outer_loop_body->InsertInstructionBefore(
        new (GetAllocator()) HInstanceFieldSet(parameter,
                                               parameter,
                                               nullptr,
                                               DataType::Type::kReference,
                                               MemberOffset(42),
                                               false,
                                               kUnknownFieldIndex,
                                               kUnknownClassDefIndex,
                                               graph->GetDexFile(),
                                               0),
        outer_loop_body->GetLastInstruction());

    SideEffectsAnalysis side_effects(graph);
    side_effects.Run();

    ASSERT_TRUE(side_effects.GetBlockEffects(entry).DoesAnyWrite());
    ASSERT_TRUE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite());
    ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite());
    ASSERT_FALSE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite());
    ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).Equals(kCanTriggerGC));
  }

  // Check that the side effects of the inner loop affects the outer loop.
  {
    outer_loop_body->RemoveInstruction(outer_loop_body->GetFirstInstruction());
    inner_loop_body->InsertInstructionBefore(
        new (GetAllocator()) HInstanceFieldSet(parameter,
                                               parameter,
                                               nullptr,
                                               DataType::Type::kReference,
                                               MemberOffset(42),
                                               false,
                                               kUnknownFieldIndex,
                                               kUnknownClassDefIndex,
                                               graph->GetDexFile(),
                                               0),
        inner_loop_body->GetLastInstruction());

    SideEffectsAnalysis side_effects(graph);
    side_effects.Run();

    ASSERT_TRUE(side_effects.GetBlockEffects(entry).DoesAnyWrite());
    ASSERT_FALSE(side_effects.GetBlockEffects(outer_loop_body).DoesAnyWrite());
    ASSERT_TRUE(side_effects.GetLoopEffects(outer_loop_header).DoesAnyWrite());
    ASSERT_TRUE(side_effects.GetLoopEffects(inner_loop_header).DoesAnyWrite());
  }
}
}  // namespace art