/*

 * Copyright (c) 2015, 2019, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * 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 "opto/castnode.hpp"

#include "opto/compile.hpp"

#include "opto/escape.hpp"

#include "opto/graphKit.hpp"

#include "opto/loopnode.hpp"

#include "opto/machnode.hpp"

#include "opto/macro.hpp"

#include "opto/memnode.hpp"

#include "opto/movenode.hpp"

#include "opto/node.hpp"

#include "opto/phase.hpp"

#include "opto/phaseX.hpp"

#include "opto/rootnode.hpp"

#include "opto/type.hpp"

#include "utilities/copy.hpp"

#include "utilities/growableArray.hpp"

#include "utilities/macros.hpp"

#include "gc/z/zBarrierSet.hpp"

#include "gc/z/c2/zBarrierSetC2.hpp"

#include "gc/z/zThreadLocalData.hpp"

#include "gc/z/zBarrierSetRuntime.hpp"

ZBarrierSetC2State::ZBarrierSetC2State(Arena* comp_arena) :

    _load_barrier_nodes(new (comp_arena) GrowableArray<LoadBarrierNode*>(comp_arena, 8,  0, NULL)) {}

int ZBarrierSetC2State::load_barrier_count() const {

  return _load_barrier_nodes->length();

}

void ZBarrierSetC2State::add_load_barrier_node(LoadBarrierNode * n) {

  assert(!_load_barrier_nodes->contains(n), " duplicate entry in expand list");

  _load_barrier_nodes->append(n);

}

void ZBarrierSetC2State::remove_load_barrier_node(LoadBarrierNode * n) {

  // this function may be called twice for a node so check

  // that the node is in the array before attempting to remove it

  if (_load_barrier_nodes->contains(n)) {

    _load_barrier_nodes->remove(n);

  }

}

LoadBarrierNode* ZBarrierSetC2State::load_barrier_node(int idx) const {

  return _load_barrier_nodes->at(idx);

}

void* ZBarrierSetC2::create_barrier_state(Arena* comp_arena) const {

  return new(comp_arena) ZBarrierSetC2State(comp_arena);

}

ZBarrierSetC2State* ZBarrierSetC2::state() const {

  return reinterpret_cast<ZBarrierSetC2State*>(Compile::current()->barrier_set_state());

}

bool ZBarrierSetC2::is_gc_barrier_node(Node* node) const {

  // 1. This step follows potential oop projections of a load barrier before expansion

  if (node->is_Proj()) {

    node = node->in(0);

  }

  // 2. This step checks for unexpanded load barriers

  if (node->is_LoadBarrier()) {

    return true;

  }

  // 3. This step checks for the phi corresponding to an optimized load barrier expansion

  if (node->is_Phi()) {

    PhiNode* phi = node->as_Phi();

    Node* n = phi->in(1);

    if (n != NULL && n->is_LoadBarrierSlowReg()) {

      return true;

    }

  }

  return false;

}

void ZBarrierSetC2::register_potential_barrier_node(Node* node) const {

  if (node->is_LoadBarrier()) {

    state()->add_load_barrier_node(node->as_LoadBarrier());

  }

}

void ZBarrierSetC2::unregister_potential_barrier_node(Node* node) const {

  if (node->is_LoadBarrier()) {

    state()->remove_load_barrier_node(node->as_LoadBarrier());

  }

}

void ZBarrierSetC2::eliminate_useless_gc_barriers(Unique_Node_List &useful, Compile* C) const {

  // Remove useless LoadBarrier nodes

  ZBarrierSetC2State* s = state();

  for (int i = s->load_barrier_count()-1; i >= 0; i--) {

    LoadBarrierNode* n = s->load_barrier_node(i);

    if (!useful.member(n)) {

      unregister_potential_barrier_node(n);

    }

  }

}

void ZBarrierSetC2::enqueue_useful_gc_barrier(PhaseIterGVN* igvn, Node* node) const {

  if (node->is_LoadBarrier() && !node->as_LoadBarrier()->has_true_uses()) {

    igvn->_worklist.push(node);

  }

}

static bool load_require_barrier(LoadNode* load)      { return ((load->barrier_data() & RequireBarrier) != 0); }

static bool load_has_weak_barrier(LoadNode* load)     { return ((load->barrier_data() & WeakBarrier) != 0); }

static bool load_has_expanded_barrier(LoadNode* load) { return ((load->barrier_data() & ExpandedBarrier) != 0); }

static void load_set_expanded_barrier(LoadNode* load) { return load->set_barrier_data(ExpandedBarrier); }

static void load_set_barrier(LoadNode* load, bool weak)    {

  if (weak) {

    load->set_barrier_data(WeakBarrier);

  } else {

    load->set_barrier_data(RequireBarrier);

  }

}

// == LoadBarrierNode ==

LoadBarrierNode::LoadBarrierNode(Compile* C,

                                 Node* c,

                                 Node* mem,

                                 Node* val,

                                 Node* adr,

                                 bool weak) :

    MultiNode(Number_of_Inputs),

    _weak(weak) {

  init_req(Control, c);

  init_req(Memory, mem);

  init_req(Oop, val);

  init_req(Address, adr);

  init_req(Similar, C->top());

  init_class_id(Class_LoadBarrier);

  BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();

  bs->register_potential_barrier_node(this);

}

uint LoadBarrierNode::size_of() const {

  return sizeof(*this);

}

bool LoadBarrierNode::cmp(const Node& n) const {

  ShouldNotReachHere();

  return false;

}

const Type *LoadBarrierNode::bottom_type() const {

  const Type** floadbarrier = (const Type **)(Compile::current()->type_arena()->Amalloc_4((Number_of_Outputs)*sizeof(Type*)));

  Node* in_oop = in(Oop);

  floadbarrier[Control] = Type::CONTROL;

  floadbarrier[Memory] = Type::MEMORY;

  floadbarrier[Oop] = in_oop == NULL ? Type::TOP : in_oop->bottom_type();

  return TypeTuple::make(Number_of_Outputs, floadbarrier);

}

const TypePtr* LoadBarrierNode::adr_type() const {

  ShouldNotReachHere();

  return NULL;

}

const Type *LoadBarrierNode::Value(PhaseGVN *phase) const {

  const Type** floadbarrier = (const Type **)(phase->C->type_arena()->Amalloc_4((Number_of_Outputs)*sizeof(Type*)));

  const Type* val_t = phase->type(in(Oop));

  floadbarrier[Control] = Type::CONTROL;

  floadbarrier[Memory]  = Type::MEMORY;

  floadbarrier[Oop]     = val_t;

  return TypeTuple::make(Number_of_Outputs, floadbarrier);

}

bool LoadBarrierNode::is_dominator(PhaseIdealLoop* phase, bool linear_only, Node *d, Node *n) {

  if (phase != NULL) {

    return phase->is_dominator(d, n);

  }

  for (int i = 0; i < 10 && n != NULL; i++) {

    n = IfNode::up_one_dom(n, linear_only);

    if (n == d) {

      return true;

    }

  }

  return false;

}

LoadBarrierNode* LoadBarrierNode::has_dominating_barrier(PhaseIdealLoop* phase, bool linear_only, bool look_for_similar) {

  if (is_weak()) {

    // Weak barriers can't be eliminated

    return NULL;

  }

  Node* val = in(LoadBarrierNode::Oop);

  if (in(Similar)->is_Proj() && in(Similar)->in(0)->is_LoadBarrier()) {

    LoadBarrierNode* lb = in(Similar)->in(0)->as_LoadBarrier();

    assert(lb->in(Address) == in(Address), "");

    // Load barrier on Similar edge dominates so if it now has the Oop field it can replace this barrier.

    if (lb->in(Oop) == in(Oop)) {

      return lb;

    }

    // Follow chain of load barrier through Similar edges

    while (!lb->in(Similar)->is_top()) {

      lb = lb->in(Similar)->in(0)->as_LoadBarrier();

      assert(lb->in(Address) == in(Address), "");

    }

    if (lb != in(Similar)->in(0)) {

      return lb;

    }

  }

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

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

    if (u != this && u->is_LoadBarrier() && u->in(Oop) == val && u->as_LoadBarrier()->has_true_uses()) {

      Node* this_ctrl = in(LoadBarrierNode::Control);

      Node* other_ctrl = u->in(LoadBarrierNode::Control);

      if (is_dominator(phase, linear_only, other_ctrl, this_ctrl)) {

        return u->as_LoadBarrier();

      }

    }

  }

  if (can_be_eliminated()) {

    return NULL;

  }

  if (!look_for_similar) {

    return NULL;

  }

  Node* addr = in(LoadBarrierNode::Address);

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

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

    if (u != this && u->is_LoadBarrier() && u->as_LoadBarrier()->has_true_uses()) {

      Node* this_ctrl = in(LoadBarrierNode::Control);

      Node* other_ctrl = u->in(LoadBarrierNode::Control);

      if (is_dominator(phase, linear_only, other_ctrl, this_ctrl)) {

        ResourceMark rm;

        Unique_Node_List wq;

        wq.push(in(LoadBarrierNode::Control));

        bool ok = true;

        bool dom_found = false;

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

          Node *n = wq.at(next);

          if (n->is_top()) {

            return NULL;

          }

          assert(n->is_CFG(), "");

          if (n->is_SafePoint()) {

            ok = false;

            break;

          }

          if (n == u) {

            dom_found = true;

            continue;

          }

          if (n->is_Region()) {

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

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

              if (m != NULL) {

                wq.push(m);

              }

            }

          } else {

            Node* m = n->in(0);

            if (m != NULL) {

              wq.push(m);

            }

          }

        }

        if (ok) {

          assert(dom_found, "");

          return u->as_LoadBarrier();

        }

        break;

      }

    }

  }

  return NULL;

}

void LoadBarrierNode::push_dominated_barriers(PhaseIterGVN* igvn) const {

  // Change to that barrier may affect a dominated barrier so re-push those

  assert(!is_weak(), "sanity");

  Node* val = in(LoadBarrierNode::Oop);

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

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

    if (u != this && u->is_LoadBarrier() && u->in(Oop) == val) {

      Node* this_ctrl = in(Control);

      Node* other_ctrl = u->in(Control);

      if (is_dominator(NULL, false, this_ctrl, other_ctrl)) {

        igvn->_worklist.push(u);

      }

    }

    Node* addr = in(LoadBarrierNode::Address);

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

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

      if (u != this && u->is_LoadBarrier() && u->in(Similar)->is_top()) {

        Node* this_ctrl = in(Control);

        Node* other_ctrl = u->in(Control);

        if (is_dominator(NULL, false, this_ctrl, other_ctrl)) {

          igvn->_worklist.push(u);

        }

      }

    }

  }

}

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

  LoadBarrierNode* dominating_barrier = has_dominating_barrier(NULL, true, false);

  if (dominating_barrier != NULL) {

    assert(!is_weak(), "Weak barriers cant be eliminated");

    assert(dominating_barrier->in(Oop) == in(Oop), "");

    return dominating_barrier;

  }

  return this;

}

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

  if (remove_dead_region(phase, can_reshape)) {

    return this;

  }

  Node *val = in(Oop);

  Node *mem = in(Memory);

  Node *ctrl = in(Control);

  assert(val->Opcode() != Op_LoadN, "");

  assert(val->Opcode() != Op_DecodeN, "");

  if (mem->is_MergeMem()) {

    Node *new_mem = mem->as_MergeMem()->memory_at(Compile::AliasIdxRaw);

    set_req(Memory, new_mem);

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

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

    }

    return this;

  }

  LoadBarrierNode *dominating_barrier = NULL;

  if (!is_weak()) {

    dominating_barrier = has_dominating_barrier(NULL, !can_reshape, !phase->C->major_progress());

    if (dominating_barrier != NULL && dominating_barrier->in(Oop) != in(Oop)) {

      assert(in(Address) == dominating_barrier->in(Address), "");

      set_req(Similar, dominating_barrier->proj_out(Oop));

      return this;

    }

  }

  bool eliminate = can_reshape && (dominating_barrier != NULL || !has_true_uses());

  if (eliminate) {

    if (can_reshape) {

      PhaseIterGVN* igvn = phase->is_IterGVN();

      Node* out_ctrl = proj_out_or_null(Control);

      Node* out_res = proj_out_or_null(Oop);

      if (out_ctrl != NULL) {

        igvn->replace_node(out_ctrl, ctrl);

      }

      // That transformation may cause the Similar edge on the load barrier to be invalid

      fix_similar_in_uses(igvn);

      if (out_res != NULL) {

        if (dominating_barrier != NULL) {

          assert(!is_weak(), "Sanity");

          igvn->replace_node(out_res, dominating_barrier->proj_out(Oop));

        } else {

          igvn->replace_node(out_res, val);

        }

      }

    }

    return new ConINode(TypeInt::ZERO);

  }

  // If the Similar edge is no longer a load barrier, clear it

  Node* similar = in(Similar);

  if (!similar->is_top() && !(similar->is_Proj() && similar->in(0)->is_LoadBarrier())) {

    set_req(Similar, phase->C->top());

    return this;

  }

  if (can_reshape && !is_weak()) {

    // If this barrier is linked through the Similar edge by a

    // dominated barrier and both barriers have the same Oop field,

    // the dominated barrier can go away, so push it for reprocessing.

    // We also want to avoid a barrier to depend on another dominating

    // barrier through its Similar edge that itself depend on another

    // barrier through its Similar edge and rather have the first

    // depend on the third.

    PhaseIterGVN* igvn = phase->is_IterGVN();

    Node* out_res = proj_out(Oop);

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

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

      if (u->is_LoadBarrier() && u->in(Similar) == out_res &&

          (u->in(Oop) == val || !u->in(Similar)->is_top())) {

        assert(!u->as_LoadBarrier()->is_weak(), "Sanity");

        igvn->_worklist.push(u);

      }

    }

    push_dominated_barriers(igvn);

  }

  return NULL;

}

uint LoadBarrierNode::match_edge(uint idx) const {

  ShouldNotReachHere();

  return 0;

}

void LoadBarrierNode::fix_similar_in_uses(PhaseIterGVN* igvn) {

  Node* out_res = proj_out_or_null(Oop);

  if (out_res == NULL) {

    return;

  }

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

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

    if (u->is_LoadBarrier() && u->in(Similar) == out_res) {

      igvn->replace_input_of(u, Similar, igvn->C->top());

      --i;

      --imax;

    }

  }

}

bool LoadBarrierNode::has_true_uses() const {

  Node* out_res = proj_out_or_null(Oop);

  if (out_res != NULL) {

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

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

      if (!u->is_LoadBarrier() || u->in(Similar) != out_res) {

        return true;

      }

    }

  }

  return false;

}

static bool barrier_needed(C2Access& access) {

  return ZBarrierSet::barrier_needed(access.decorators(), access.type());

}

Node* ZBarrierSetC2::load_at_resolved(C2Access& access, const Type* val_type) const {

  Node* p = BarrierSetC2::load_at_resolved(access, val_type);

  if (!barrier_needed(access)) {

    return p;

  }

  bool weak = (access.decorators() & ON_WEAK_OOP_REF) != 0;

  if (p->isa_Load()) {

    load_set_barrier(p->as_Load(), weak);

  }

  return p;

}

Node* ZBarrierSetC2::atomic_cmpxchg_val_at_resolved(C2AtomicParseAccess& access, Node* expected_val,

                                                    Node* new_val, const Type* val_type) const {

  Node* result = BarrierSetC2::atomic_cmpxchg_val_at_resolved(access, expected_val, new_val, val_type);

  LoadStoreNode* lsn = result->as_LoadStore();

  if (barrier_needed(access)) {

    lsn->set_has_barrier();

  }

  return lsn;

}

Node* ZBarrierSetC2::atomic_cmpxchg_bool_at_resolved(C2AtomicParseAccess& access, Node* expected_val,

                                                     Node* new_val, const Type* value_type) const {

  Node* result = BarrierSetC2::atomic_cmpxchg_bool_at_resolved(access, expected_val, new_val, value_type);

  LoadStoreNode* lsn = result->as_LoadStore();

  if (barrier_needed(access)) {

    lsn->set_has_barrier();

  }

  return lsn;

}

Node* ZBarrierSetC2::atomic_xchg_at_resolved(C2AtomicParseAccess& access, Node* new_val, const Type* val_type) const {

  Node* result = BarrierSetC2::atomic_xchg_at_resolved(access, new_val, val_type);

  LoadStoreNode* lsn = result->as_LoadStore();

  if (barrier_needed(access)) {

    lsn->set_has_barrier();

  }

  return lsn;

}

// == Macro Expansion ==