/*

 * Copyright (c) 2015, 2018, Red Hat, Inc. All rights reserved.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#include "precompiled.hpp"

#include "gc/shenandoah/c2/shenandoahSupport.hpp"

#include "gc/shenandoah/c2/shenandoahBarrierSetC2.hpp"

#include "gc/shenandoah/shenandoahBarrierSetAssembler.hpp"

#include "gc/shenandoah/shenandoahBrooksPointer.hpp"

#include "gc/shenandoah/shenandoahHeap.hpp"

#include "gc/shenandoah/shenandoahHeapRegion.hpp"

#include "gc/shenandoah/shenandoahRuntime.hpp"

#include "opto/arraycopynode.hpp"

#include "opto/block.hpp"

#include "opto/callnode.hpp"

#include "opto/castnode.hpp"

#include "opto/movenode.hpp"

#include "opto/phaseX.hpp"

#include "opto/rootnode.hpp"

#include "opto/runtime.hpp"

#include "opto/subnode.hpp"

Node* ShenandoahBarrierNode::skip_through_barrier(Node* n) {

  if (n == NULL) {

    return NULL;

  }

  if (n->Opcode() == Op_ShenandoahEnqueueBarrier) {

    n = n->in(1);

  }

  if (n->is_ShenandoahBarrier()) {

    return n->in(ValueIn);

  } else if (n->is_Phi() &&

             n->req() == 3 &&

             n->in(1) != NULL &&

             n->in(1)->is_ShenandoahBarrier() &&

             n->in(2) != NULL &&

             n->in(2)->bottom_type() == TypePtr::NULL_PTR &&

             n->in(0) != NULL &&

             n->in(0)->in(1) != NULL &&

             n->in(0)->in(1)->is_IfProj() &&

             n->in(0)->in(2) != NULL &&

             n->in(0)->in(2)->is_IfProj() &&

             n->in(0)->in(1)->in(0) != NULL &&

             n->in(0)->in(1)->in(0) == n->in(0)->in(2)->in(0) &&

             n->in(1)->in(ValueIn)->Opcode() == Op_CastPP) {

    Node* iff = n->in(0)->in(1)->in(0);

    Node* res = n->in(1)->in(ValueIn)->in(1);

    if (iff->is_If() &&

        iff->in(1) != NULL &&

        iff->in(1)->is_Bool() &&

        iff->in(1)->as_Bool()->_test._test == BoolTest::ne &&

        iff->in(1)->in(1) != NULL &&

        iff->in(1)->in(1)->Opcode() == Op_CmpP &&

        iff->in(1)->in(1)->in(1) != NULL &&

        iff->in(1)->in(1)->in(1) == res &&

        iff->in(1)->in(1)->in(2) != NULL &&

        iff->in(1)->in(1)->in(2)->bottom_type() == TypePtr::NULL_PTR) {

      return res;

    }

  }

  return n;

}

bool ShenandoahBarrierNode::needs_barrier(PhaseGVN* phase, ShenandoahBarrierNode* orig, Node* n, Node* rb_mem, bool allow_fromspace) {

  Unique_Node_List visited;

  return needs_barrier_impl(phase, orig, n, rb_mem, allow_fromspace, visited);

}

bool ShenandoahBarrierNode::needs_barrier_impl(PhaseGVN* phase, ShenandoahBarrierNode* orig, Node* n, Node* rb_mem, bool allow_fromspace, Unique_Node_List &visited) {

  if (visited.member(n)) {

    return false; // Been there.

  }

  visited.push(n);

  if (n->is_Allocate()) {

    return false;

  }

  if (n->is_Call()) {

    return true;

  }

  const Type* type = phase->type(n);

  if (type == Type::TOP) {

    return false;

  }

  if (type->make_ptr()->higher_equal(TypePtr::NULL_PTR)) {

    return false;

  }

  if (type->make_oopptr() && type->make_oopptr()->const_oop() != NULL) {

    return false;

  }

  if (ShenandoahOptimizeStableFinals) {

    const TypeAryPtr* ary = type->isa_aryptr();

    if (ary && ary->is_stable() && allow_fromspace) {

      return false;

    }

  }

  if (n->is_CheckCastPP() || n->is_ConstraintCast() || n->Opcode() == Op_ShenandoahEnqueueBarrier) {

    return needs_barrier_impl(phase, orig, n->in(1), rb_mem, allow_fromspace, visited);

  }

  if (n->is_Parm()) {

    return true;

  }

  if (n->is_Proj()) {

    return needs_barrier_impl(phase, orig, n->in(0), rb_mem, allow_fromspace, visited);

  }

  if (n->Opcode() == Op_ShenandoahWBMemProj) {

    return needs_barrier_impl(phase, orig, n->in(ShenandoahWBMemProjNode::WriteBarrier), rb_mem, allow_fromspace, visited);

  }

  if (n->is_Phi()) {

    bool need_barrier = false;

    for (uint i = 1; i < n->req() && ! need_barrier; i++) {

      Node* input = n->in(i);

      if (input == NULL) {

        need_barrier = true; // Phi not complete yet?

      } else if (needs_barrier_impl(phase, orig, input, rb_mem, allow_fromspace, visited)) {

        need_barrier = true;

      }

    }

    return need_barrier;

  }

  if (n->is_CMove()) {

    return needs_barrier_impl(phase, orig, n->in(CMoveNode::IfFalse), rb_mem, allow_fromspace, visited) ||

           needs_barrier_impl(phase, orig, n->in(CMoveNode::IfTrue ), rb_mem, allow_fromspace, visited);

  }

  if (n->Opcode() == Op_CreateEx) {

    return true;

  }

  if (n->Opcode() == Op_ShenandoahWriteBarrier) {

    return false;

  }

  if (n->Opcode() == Op_ShenandoahReadBarrier) {

    if (rb_mem == n->in(Memory)) {

      return false;

    } else {

      return true;

    }

  }

  if (n->Opcode() == Op_LoadP ||

      n->Opcode() == Op_LoadN ||

      n->Opcode() == Op_GetAndSetP ||

      n->Opcode() == Op_CompareAndExchangeP ||

      n->Opcode() == Op_ShenandoahCompareAndExchangeP ||

      n->Opcode() == Op_GetAndSetN ||

      n->Opcode() == Op_CompareAndExchangeN ||

      n->Opcode() == Op_ShenandoahCompareAndExchangeN) {

    return true;

  }

  if (n->Opcode() == Op_DecodeN ||

      n->Opcode() == Op_EncodeP) {

    return needs_barrier_impl(phase, orig, n->in(1), rb_mem, allow_fromspace, visited);

  }

#ifdef ASSERT

  tty->print("need barrier on?: "); n->dump();

  ShouldNotReachHere();

#endif

  return true;

}

bool ShenandoahReadBarrierNode::dominates_memory_rb_impl(PhaseGVN* phase,

                                                         Node* b1,

                                                         Node* b2,

                                                         Node* current,

                                                         bool linear) {

  ResourceMark rm;

  VectorSet visited(Thread::current()->resource_area());

  Node_Stack phis(0);

  for(int i = 0; i < 10; i++) {

    if (current == NULL) {

      return false;

    } else if (visited.test_set(current->_idx) || current->is_top() || current == b1) {

      current = NULL;

      while (phis.is_nonempty() && current == NULL) {

        uint idx = phis.index();

        Node* phi = phis.node();

        if (idx >= phi->req()) {

          phis.pop();

        } else {

          current = phi->in(idx);

          phis.set_index(idx+1);

        }

      }

      if (current == NULL) {

        return true;

      }

    } else if (current == phase->C->immutable_memory()) {

      return false;

    } else if (current->isa_Phi()) {

      if (!linear) {

        return false;

      }

      phis.push(current, 2);

      current = current->in(1);

    } else if (current->Opcode() == Op_ShenandoahWriteBarrier) {

      const Type* in_type = current->bottom_type();

      const Type* this_type = b2->bottom_type();

      if (is_independent(in_type, this_type)) {

        current = current->in(Memory);

      } else {

        return false;

      }

    } else if (current->Opcode() == Op_ShenandoahWBMemProj) {

      current = current->in(ShenandoahWBMemProjNode::WriteBarrier);

    } else if (current->is_Proj()) {

      current = current->in(0);

    } else if (current->is_Call()) {

      return false; // TODO: Maybe improve by looking at the call's memory effects?

    } else if (current->is_MemBar()) {

      return false; // TODO: Do we need to stop at *any* membar?

    } else if (current->is_MergeMem()) {

      const TypePtr* adr_type = brooks_pointer_type(phase->type(b2));

      uint alias_idx = phase->C->get_alias_index(adr_type);

      current = current->as_MergeMem()->memory_at(alias_idx);

    } else {

#ifdef ASSERT

      current->dump();

#endif

      ShouldNotReachHere();

      return false;

    }

  }

  return false;

}

bool ShenandoahReadBarrierNode::is_independent(Node* mem) {

  if (mem->is_Phi() || mem->is_Proj() || mem->is_MergeMem()) {

    return true;

  } else if (mem->Opcode() == Op_ShenandoahWBMemProj) {

    return true;

  } else if (mem->Opcode() == Op_ShenandoahWriteBarrier) {

    const Type* mem_type = mem->bottom_type();

    const Type* this_type = bottom_type();

    if (is_independent(mem_type, this_type)) {

      return true;

    } else {

      return false;

    }

  } else if (mem->is_Call() || mem->is_MemBar()) {

    return false;

  }

#ifdef ASSERT

  mem->dump();

#endif

  ShouldNotReachHere();

  return true;

}

bool ShenandoahReadBarrierNode::dominates_memory_rb(PhaseGVN* phase, Node* b1, Node* b2, bool linear) {

  return dominates_memory_rb_impl(phase, b1->in(Memory), b2, b2->in(Memory), linear);

}

bool ShenandoahReadBarrierNode::is_independent(const Type* in_type, const Type* this_type) {

  assert(in_type->isa_oopptr(), "expect oop ptr");

  assert(this_type->isa_oopptr(), "expect oop ptr");

  ciKlass* in_kls = in_type->is_oopptr()->klass();

  ciKlass* this_kls = this_type->is_oopptr()->klass();

  if (in_kls != NULL && this_kls != NULL &&

      in_kls->is_loaded() && this_kls->is_loaded() &&

      (!in_kls->is_subclass_of(this_kls)) &&

      (!this_kls->is_subclass_of(in_kls))) {

    return true;

  }

  return false;

}

Node* ShenandoahReadBarrierNode::Ideal(PhaseGVN *phase, bool can_reshape) {

  if (! can_reshape) {

    return NULL;

  }

  if (in(Memory) == phase->C->immutable_memory()) return NULL;

  // If memory input is a MergeMem, take the appropriate slice out of it.

  Node* mem_in = in(Memory);

  if (mem_in->isa_MergeMem()) {

    const TypePtr* adr_type = brooks_pointer_type(bottom_type());

    uint alias_idx = phase->C->get_alias_index(adr_type);

    mem_in = mem_in->as_MergeMem()->memory_at(alias_idx);

    set_req(Memory, mem_in);

    return this;

  }

  Node* input = in(Memory);

  if (input->Opcode() == Op_ShenandoahWBMemProj) {

    ResourceMark rm;

    VectorSet seen(Thread::current()->resource_area());

    Node* n = in(Memory);

    while (n->Opcode() == Op_ShenandoahWBMemProj &&

           n->in(ShenandoahWBMemProjNode::WriteBarrier) != NULL &&

           n->in(ShenandoahWBMemProjNode::WriteBarrier)->Opcode() == Op_ShenandoahWriteBarrier &&

           n->in(ShenandoahWBMemProjNode::WriteBarrier)->in(Memory) != NULL) {

      if (seen.test_set(n->_idx)) {

        return NULL; // loop

      }

      n = n->in(ShenandoahWBMemProjNode::WriteBarrier)->in(Memory);

    }

    Node* wb = input->in(ShenandoahWBMemProjNode::WriteBarrier);

    const Type* in_type = phase->type(wb);

    // is_top() test not sufficient here: we can come here after CCP

    // in a dead branch of the graph that has not yet been removed.

    if (in_type == Type::TOP) return NULL; // Dead path.

    assert(wb->Opcode() == Op_ShenandoahWriteBarrier, "expect write barrier");

    if (is_independent(in_type, _type)) {

      phase->igvn_rehash_node_delayed(wb);

      set_req(Memory, wb->in(Memory));

      if (can_reshape && input->outcnt() == 0) {

        phase->is_IterGVN()->_worklist.push(input);

      }

      return this;

    }

  }

  return NULL;

}

ShenandoahWriteBarrierNode::ShenandoahWriteBarrierNode(Compile* C, Node* ctrl, Node* mem, Node* obj)

  : ShenandoahBarrierNode(ctrl, mem, obj, false) {

  assert(UseShenandoahGC && ShenandoahWriteBarrier, "should be enabled");

  ShenandoahBarrierSetC2::bsc2()->state()->add_shenandoah_barrier(this);

}

Node* ShenandoahWriteBarrierNode::Identity(PhaseGVN* phase) {

  assert(in(0) != NULL, "should have control");

  PhaseIterGVN* igvn = phase->is_IterGVN();

  Node* mem_in = in(Memory);

  Node* mem_proj = NULL;

  if (igvn != NULL) {

    mem_proj = find_out_with(Op_ShenandoahWBMemProj);

    if (mem_in == mem_proj) {

      return this;

    }

  }

  Node* replacement = Identity_impl(phase);

  if (igvn != NULL) {

    if (replacement != NULL && replacement != this && mem_proj != NULL) {

      igvn->replace_node(mem_proj, mem_in);

    }

  }

  return replacement;

}

Node* ShenandoahWriteBarrierNode::Ideal(PhaseGVN *phase, bool can_reshape) {

  assert(in(0) != NULL, "should have control");

  if (!can_reshape) {

    return NULL;

  }

  Node* mem_in = in(Memory);

  if (mem_in->isa_MergeMem()) {

    const TypePtr* adr_type = brooks_pointer_type(bottom_type());

    uint alias_idx = phase->C->get_alias_index(adr_type);

    mem_in = mem_in->as_MergeMem()->memory_at(alias_idx);

    set_req(Memory, mem_in);

    return this;

  }

  Node* val = in(ValueIn);

  if (val->is_ShenandoahBarrier()) {

    set_req(ValueIn, val->in(ValueIn));

    return this;

  }

  return NULL;

}

bool ShenandoahWriteBarrierNode::expand(Compile* C, PhaseIterGVN& igvn) {

  if (UseShenandoahGC) {

    if (ShenandoahBarrierSetC2::bsc2()->state()->shenandoah_barriers_count() > 0 || (!ShenandoahWriteBarrier && ShenandoahStoreValEnqueueBarrier)) {

      bool attempt_more_loopopts = ShenandoahLoopOptsAfterExpansion;

      C->clear_major_progress();

      PhaseIdealLoop ideal_loop(igvn, LoopOptsShenandoahExpand);

      if (C->failing()) return false;

      PhaseIdealLoop::verify(igvn);

      DEBUG_ONLY(ShenandoahBarrierNode::verify_raw_mem(C->root());)

      if (attempt_more_loopopts) {

        C->set_major_progress();

        if (!C->optimize_loops(igvn, LoopOptsShenandoahPostExpand)) {

          return false;

        }

        C->clear_major_progress();

      }

    }

  }

  return true;

}

bool ShenandoahWriteBarrierNode::is_heap_state_test(Node* iff, int mask) {

  if (!UseShenandoahGC) {

    return false;

  }

  assert(iff->is_If(), "bad input");

  if (iff->Opcode() != Op_If) {

    return false;

  }

  Node* bol = iff->in(1);

  if (!bol->is_Bool() || bol->as_Bool()->_test._test != BoolTest::ne) {

    return false;

  }

  Node* cmp = bol->in(1);

  if (cmp->Opcode() != Op_CmpI) {

    return false;

  }

  Node* in1 = cmp->in(1);

  Node* in2 = cmp->in(2);

  if (in2->find_int_con(-1) != 0) {

    return false;

  }

  if (in1->Opcode() != Op_AndI) {

    return false;

  }

  in2 = in1->in(2);

  if (in2->find_int_con(-1) != mask) {

    return false;

  }

  in1 = in1->in(1);

  return is_gc_state_load(in1);

}

bool ShenandoahWriteBarrierNode::is_heap_stable_test(Node* iff) {

  return is_heap_state_test(iff, ShenandoahHeap::HAS_FORWARDED);

}

bool ShenandoahWriteBarrierNode::is_gc_state_load(Node *n) {

  if (!UseShenandoahGC) {

    return false;

  }

  if (n->Opcode() != Op_LoadB && n->Opcode() != Op_LoadUB) {

    return false;

  }

  Node* addp = n->in(MemNode::Address);

  if (!addp->is_AddP()) {

    return false;

  }

  Node* base = addp->in(AddPNode::Address);

  Node* off = addp->in(AddPNode::Offset);

  if (base->Opcode() != Op_ThreadLocal) {

    return false;

  }

  if (off->find_intptr_t_con(-1) != in_bytes(ShenandoahThreadLocalData::gc_state_offset())) {

    return false;

  }

  return true;

}

bool ShenandoahWriteBarrierNode::has_safepoint_between(Node* start, Node* stop, PhaseIdealLoop *phase) {

  assert(phase->is_dominator(stop, start), "bad inputs");

  ResourceMark rm;

  Unique_Node_List wq;

  wq.push(start);

  for (uint next = 0; next < wq.size(); next++) {

    Node *m = wq.at(next);

    if (m == stop) {

      continue;

    }

    if (m->is_SafePoint() && !m->is_CallLeaf()) {

      return true;

    }

    if (m->is_Region()) {

      for (uint i = 1; i < m->req(); i++) {

        wq.push(m->in(i));

      }

    } else {

      wq.push(m->in(0));

    }

  }

  return false;

}

bool ShenandoahWriteBarrierNode::try_common_gc_state_load(Node *n, PhaseIdealLoop *phase) {

  assert(is_gc_state_load(n), "inconsistent");

  Node* addp = n->in(MemNode::Address);

  Node* dominator = NULL;

  for (DUIterator_Fast imax, i = addp->fast_outs(imax); i < imax; i++) {

    Node* u = addp->fast_out(i);

    assert(is_gc_state_load(u), "inconsistent");

    if (u != n && phase->is_dominator(u->in(0), n->in(0))) {

      if (dominator == NULL) {

        dominator = u;

      } else {

        if (phase->dom_depth(u->in(0)) < phase->dom_depth(dominator->in(0))) {

          dominator = u;

        }

      }

    }

  }

  if (dominator == NULL || has_safepoint_between(n->in(0), dominator->in(0), phase)) {

    return false;

  }

  phase->igvn().replace_node(n, dominator);

  return true;

}

bool ShenandoahBarrierNode::dominates_memory_impl(PhaseGVN* phase,

                                                  Node* b1,