/*

 * Copyright (c) 2015, 2018, 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/compile.hpp"

#include "opto/castnode.hpp"

#include "opto/graphKit.hpp"

#include "opto/idealKit.hpp"

#include "opto/loopnode.hpp"

#include "opto/macro.hpp"

#include "opto/node.hpp"

#include "opto/type.hpp"

#include "utilities/macros.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() ||  n->is_LoadBarrierWeakSlowReg())) {

      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);

  }

}

void ZBarrierSetC2::find_dominating_barriers(PhaseIterGVN& igvn) {

  // Look for dominating barriers on the same address only once all

  // other loop opts are over: loop opts may cause a safepoint to be

  // inserted between a barrier and its dominating barrier.

  Compile* C = Compile::current();

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

  ZBarrierSetC2State* s = bs->state();

  if (s->load_barrier_count() >= 2) {

    Compile::TracePhase tp("idealLoop", &C->timers[Phase::_t_idealLoop]);

    PhaseIdealLoop ideal_loop(igvn, LoopOptsLastRound);

    if (C->major_progress()) C->print_method(PHASE_PHASEIDEALLOOP_ITERATIONS, 2);

  }

}

void ZBarrierSetC2::add_users_to_worklist(Unique_Node_List* worklist) const {

  // Permanent temporary workaround

  // Loadbarriers may have non-obvious dead uses keeping them alive during parsing. The use is

  // removed by RemoveUseless (after parsing, before optimize) but the barriers won't be added to

  // the worklist. Unless we add them explicitly they are not guaranteed to end up there.

  ZBarrierSetC2State* s = state();

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

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

    worklist->push(n);

  }

}

const TypeFunc* ZBarrierSetC2::load_barrier_Type() const {

  const Type** fields;

  // Create input types (domain)

  fields = TypeTuple::fields(2);

  fields[TypeFunc::Parms+0] = TypeInstPtr::NOTNULL;

  fields[TypeFunc::Parms+1] = TypeOopPtr::BOTTOM;

  const TypeTuple *domain = TypeTuple::make(TypeFunc::Parms+2, fields);

  // Create result type (range)

  fields = TypeTuple::fields(1);

  fields[TypeFunc::Parms+0] = TypeInstPtr::BOTTOM;

  const TypeTuple *range = TypeTuple::make(TypeFunc::Parms+1, fields);

  return TypeFunc::make(domain, range);

}

// == LoadBarrierNode ==

LoadBarrierNode::LoadBarrierNode(Compile* C,

                                 Node* c,

                                 Node* mem,

                                 Node* val,

                                 Node* adr,

                                 bool weak,

                                 bool writeback,

                                 bool oop_reload_allowed) :

    MultiNode(Number_of_Inputs),

    _weak(weak),

    _writeback(writeback),

    _oop_reload_allowed(oop_reload_allowed) {

  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);

}

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 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) {

  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 (ZVerifyLoadBarriers || 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

  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) {

  if (!phase->C->directive()->ZOptimizeLoadBarriersOption) {

    return this;

  }

  bool redundant_addr = false;

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

  if (dominating_barrier != NULL) {

    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);

  Node* adr = in(Address);

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

  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;

  }

  bool optimizeLoadBarriers = phase->C->directive()->ZOptimizeLoadBarriersOption;

  LoadBarrierNode* dominating_barrier = optimizeLoadBarriers ? has_dominating_barrier(NULL, !can_reshape, !phase->C->major_progress()) : NULL;

  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 = (optimizeLoadBarriers && !(val->is_Phi() || val->Opcode() == Op_LoadP || val->Opcode() == Op_GetAndSetP || val->is_DecodeN())) ||

                   (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) {

          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) {

    // 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())) {

        igvn->_worklist.push(u);

      }

    }

    push_dominated_barriers(igvn);

  }

  return NULL;

}

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) {

    return false;

  }

  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;

}

// == Accesses ==

Node* ZBarrierSetC2::make_cas_loadbarrier(C2AtomicParseAccess& access) const {

  assert(!UseCompressedOops, "Not allowed");

  CompareAndSwapNode* cas = (CompareAndSwapNode*)access.raw_access();

  PhaseGVN& gvn = access.gvn();

  Compile* C = Compile::current();

  GraphKit* kit = access.kit();

  Node* in_ctrl     = cas->in(MemNode::Control);

  Node* in_mem      = cas->in(MemNode::Memory);

  Node* in_adr      = cas->in(MemNode::Address);

  Node* in_val      = cas->in(MemNode::ValueIn);

  Node* in_expected = cas->in(LoadStoreConditionalNode::ExpectedIn);

  float likely                   = PROB_LIKELY(0.999);

  const TypePtr *adr_type        = gvn.type(in_adr)->isa_ptr();

  Compile::AliasType* alias_type = C->alias_type(adr_type);

  int alias_idx                  = C->get_alias_index(adr_type);

  // Outer check - true: continue, false: load and check

  Node* region   = new RegionNode(3);

  Node* phi      = new PhiNode(region, TypeInt::BOOL);

  Node* phi_mem  = new PhiNode(region, Type::MEMORY, adr_type);

  // Inner check - is the healed ref equal to the expected

  Node* region2  = new RegionNode(3);

  Node* phi2     = new PhiNode(region2, TypeInt::BOOL);

  Node* phi_mem2 = new PhiNode(region2, Type::MEMORY, adr_type);

  // CAS node returns 0 or 1

  Node* cmp     = gvn.transform(new CmpINode(cas, kit->intcon(0)));

  Node* bol     = gvn.transform(new BoolNode(cmp, BoolTest::ne))->as_Bool();

  IfNode* iff   = gvn.transform(new IfNode(in_ctrl, bol, likely, COUNT_UNKNOWN))->as_If();

  Node* then    = gvn.transform(new IfTrueNode(iff));

  Node* elsen   = gvn.transform(new IfFalseNode(iff));

  Node* scmemproj1   = gvn.transform(new SCMemProjNode(cas));

  kit->set_memory(scmemproj1, alias_idx);

  phi_mem->init_req(1, scmemproj1);

  phi_mem2->init_req(2, scmemproj1);

  // CAS fail - reload and heal oop

  Node* reload      = kit->make_load(elsen, in_adr, TypeOopPtr::BOTTOM, T_OBJECT, MemNode::unordered);

  Node* barrier     = gvn.transform(new LoadBarrierNode(C, elsen, scmemproj1, reload, in_adr, false, true, false));

  Node* barrierctrl = gvn.transform(new ProjNode(barrier, LoadBarrierNode::Control));

  Node* barrierdata = gvn.transform(new ProjNode(barrier, LoadBarrierNode::Oop));

  // Check load

  Node* tmpX    = gvn.transform(new CastP2XNode(NULL, barrierdata));