/*
 * Copyright (c) 2026, 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 "opto/c2_MacroAssembler.hpp"
#include "opto/callnode.hpp"
#include "opto/compile.hpp"
#include "opto/loopnode.hpp"
#include "opto/phaseX.hpp"
#include "opto/reachability.hpp"
#include "opto/regalloc.hpp"
#include "opto/runtime.hpp"
#include "utilities/pair.hpp"

/*
 * java.lang.ref.Reference::reachabilityFence support.
 *
 * Reachability Fence (RF) ensures that the given object (referent) remains strongly reachable
 * regardless of any optimizing transformations the virtual machine may perform that might otherwise
 * allow the object to become unreachable.
 *
 * RFs are intended to be used in performance-critical code, so the primary goal for C2 support is
 * to reduce their runtime overhead as much as possible.
 *
 * Reference::reachabilityFence() calls are intrinsified into ReachabilityFence CFG nodes. RF node keeps
 * its referent alive, so the referent's location is recorded at every safepoint (in its oop map) which
 * interferes with referent's live range.
 *
 * It is tempting to directly attach referents to interfering safepoints right from the beginning, but it
 * doesn't play well with some optimizations C2 does (e.g., during loop-invariant code motion a safepoint
 * can become interfering once a load is hoisted).
 *
 * Instead, reachability representation transitions through multiple phases:
 *   (0) initial set of RFs is materialized during parsing (as a result of
 *       Reference.reachabilityFence intrinsification);
 *   (1) optimization pass during loop opts eliminates redundant RF nodes and
 *       moves the ones with loop-invariant referents outside (after) loops;
 *   (2) after loop opts are over, RF nodes are eliminated and their referents are transferred to
 *       safepoint nodes (appended as edges after debug info);
 *   (3) during final graph reshaping, referent edges are removed from safepoints and materialized as RF nodes
 *       attached to their safepoint node (closely following it in CFG graph).
 *
 * Some implementation considerations.
 *
 * (a) It looks attractive to get rid of RF nodes early and transfer to safepoint-attached representation,
 * but it is not correct until loop opts are done.
 *
 * Live ranges of values are routinely extended during loop opts. And it can break the invariant that
 * all interfering safepoints contain the referent in their oop map. (If an interfering safepoint doesn't
 * keep the referent alive, then it becomes possible for the referent to be prematurely GCed.)
 *
 * compiler/c2/TestReachabilityFence.java demonstrates a situation where a load is hoisted out of a loop thus
 * extending the live range of the value it produces beyond the safepoint on loop-back edge.
 *
 * After loop opts are over, it becomes possible to reliably enumerate all interfering safepoints and
 * to ensure that the referent is present in their oop maps. Current assumption is that after loop opts the IR graph
 * is stable enough, so relative order of memory operations and safepoints is preserved and only safepoints between
 * a referent and it's uses are taken into account. A more conservative analysis can be employed -- any safepoint dominated
 * by a referent is treated as interfering with it -- if it turns out that the assumption doesn't hold.
 *
 * (b) RF nodes may interfere with Register Allocator (RA). If a safepoint is pruned during macro expansion,
 * it can make some RF nodes redundant, but we don't have information about their relations anymore to detect that.
 * Redundant RF node unnecessarily extends referent's live range and increases register pressure.
 *
 * Hence, we eliminate RF nodes and transfer their referents to corresponding safepoints (phase #2).
 * When safepoints are pruned, corresponding reachability edges also go away.
 *
 * (c) Unfortunately, it's not straightforward to stay with safepoint-attached representation till the very end,
 * because information about derived oops is attached to safepoints in a similar way. So, for now RFs are
 * rematerialized at safepoints before RA (phase #3).
 */

bool ReachabilityFenceNode::is_redundant(PhaseGVN& gvn) {
  const Type* referent_t = gvn.type(referent());
  if (referent_t == TypePtr::NULL_PTR) {
    return true; // no-op fence: null referent
  }
  if (!OptimizeReachabilityFences) {
    return false; // keep reachability fence nodes intact
  }
  if (!PreserveReachabilityFencesOnConstants && referent_t->singleton()) {
    return true; // no-op fence: constants are strongly reachable
  }
  return false;
}

Node* ReachabilityFenceNode::Ideal(PhaseGVN* phase, bool can_reshape) {
  return (remove_dead_region(phase, can_reshape) ? this : nullptr);
}

Node* ReachabilityFenceNode::Identity(PhaseGVN* phase) {
  if (is_redundant(*phase)) {
    return in(0);
  }
  return this;
}

// Turn the RF node into a no-op by setting its referent to null.
// Subsequent IGVN pass removes cleared nodes.
bool ReachabilityFenceNode::clear_referent(PhaseIterGVN& phase) {
  if (phase.type(referent()) == TypePtr::NULL_PTR) {
    return false;
  } else {
    phase.replace_input_of(this, 1, phase.makecon(TypePtr::NULL_PTR));
    return true;
  }
}

#ifndef PRODUCT
static void rf_desc(outputStream* st, const ReachabilityFenceNode* rf, PhaseRegAlloc* ra) {
  char buf[50];
  ra->dump_register(rf->referent(), buf, sizeof(buf));
  st->print("reachability fence [%s]", buf);
}

void ReachabilityFenceNode::format(PhaseRegAlloc* ra, outputStream* st) const {
  rf_desc(st, this, ra);
}

void ReachabilityFenceNode::emit(C2_MacroAssembler* masm, PhaseRegAlloc* ra) const {
  ResourceMark rm;
  stringStream ss;
  rf_desc(&ss, this, ra);
  const char* desc = masm->code_string(ss.freeze());
  masm->block_comment(desc);
}
#endif

// Detect safepoint nodes which are important for reachability tracking purposes.
// Some SafePoint nodes can't affect referent's reachability in any noticeable way and
// can be safely ignored during the analysis.
static bool is_interfering_sfpt_candidate(SafePointNode* sfpt) {
  if (sfpt->jvms() == nullptr) {
    return false; // not a real safepoint
  } else if (sfpt->is_CallStaticJava() && sfpt->as_CallStaticJava()->is_uncommon_trap()) {
    return false; // uncommon traps are exit points
  }
  return true; // a full-blown safepoint can interfere with a reachability fence and its referent
}

void PhaseIdealLoop::insert_rf(Node* ctrl, Node* referent) {
  IdealLoopTree* lpt = get_loop(ctrl);
  Node* ctrl_end = ctrl->unique_ctrl_out();

  auto new_rf = new ReachabilityFenceNode(C, ctrl, referent);

  register_control(new_rf, lpt, ctrl);
  set_idom(new_rf, ctrl, dom_depth(ctrl) + 1);
  lpt->register_reachability_fence(new_rf);

  igvn().rehash_node_delayed(ctrl_end);
  ctrl_end->replace_edge(ctrl, new_rf);

  if (idom(ctrl_end) == ctrl) {
    set_idom(ctrl_end, new_rf, dom_depth(new_rf) + 1);
  } else {
    assert(ctrl_end->is_Region(), "");
  }
}

void PhaseIdealLoop::replace_rf(Node* old_node, Node* new_node) {
  assert(old_node->is_ReachabilityFence() ||
         (old_node->is_Proj() && old_node->in(0)->is_ReachabilityFence()),
         "%s", NodeClassNames[old_node->Opcode()]);

  IdealLoopTree* lpt = get_loop(old_node);
  lpt->_body.yank(old_node);
  assert(lpt->_reachability_fences != nullptr, "missing");
  assert(lpt->_reachability_fences->contains(old_node), "missing");
  lpt->_reachability_fences->yank(old_node);
  replace_node_and_forward_ctrl(old_node, new_node);
}

void PhaseIdealLoop::remove_rf(ReachabilityFenceNode* rf) {
  Node* rf_ctrl_in = rf->in(0);
  Node* referent = rf->referent();
  if (rf->clear_referent(igvn()) && referent->outcnt() == 0) {
    remove_dead_data_node(referent);
  }
  replace_rf(rf, rf_ctrl_in);
}

//======================================================================
//---------------------------- Phase 1 ---------------------------------
// Optimization pass over reachability fences during loop opts.
// Moves RFs with loop-invariant referents out of the loop.
bool PhaseIdealLoop::optimize_reachability_fences() {
  Compile::TracePhase tp(_t_reachability_optimize);

  assert(OptimizeReachabilityFences, "required");

  // ResourceMark rm; // NB! not safe because insert_rf may trigger _idom reallocation
  Unique_Node_List redundant_rfs;
  typedef Pair<Node*,Node*> LoopExit;
  GrowableArray<LoopExit> worklist;

  for (int i = 0; i < C->reachability_fences_count(); i++) {
    ReachabilityFenceNode* rf = C->reachability_fence(i);
    assert(!rf->is_redundant(igvn()), "required");
    // Move RFs out of counted loops when possible.
    IdealLoopTree* lpt = get_loop(rf);
    Node* referent = rf->referent();
    if (lpt->is_invariant(referent)) {
      IfFalseNode* unique_loop_exit = lpt->unique_loop_exit_proj_or_null();
      if (unique_loop_exit != nullptr) {
        // Skip over an outer strip-mined loop.
        if (!lpt->is_root()) {
          IdealLoopTree* outer_lpt = lpt->_parent;
          if (outer_lpt->head()->is_OuterStripMinedLoop()) {
            if (outer_lpt->is_invariant(referent)) {
              IfNode* outer_loop_end = outer_lpt->head()->as_OuterStripMinedLoop()->outer_loop_end();
              if (outer_loop_end != nullptr && outer_loop_end->false_proj_or_null() != nullptr) {
                unique_loop_exit = outer_loop_end->false_proj_or_null();
              }
            } else {
              // An attempt to insert an RF node inside outer strip-mined loop breaks
              // its IR invariants and manifests as assertion failures.
              assert(false, "not loop invariant in outer strip-mined loop");
              continue; // skip
            }
          }
        }

        LoopExit p(referent, unique_loop_exit);
        worklist.push(p);
        redundant_rfs.push(rf);

#ifndef PRODUCT
        if (TraceLoopOpts) {
          IdealLoopTree* loop = get_loop(unique_loop_exit->in(0));
          tty->print_cr("ReachabilityFence: N%d: %s N%d/N%d -> loop exit N%d (%s N%d/N%d)",
                        rf->_idx, lpt->head()->Name(), lpt->head()->_idx, lpt->tail()->_idx,
                        unique_loop_exit->_idx,
                        loop->head()->Name(), loop->head()->_idx, loop->tail()->_idx);
        }
#endif // !PRODUCT
      }
    }
  }

  // Populate RFs outside loops.
  while (worklist.is_nonempty()) {
    LoopExit p = worklist.pop();
    Node* referent = p.first;
    Node* ctrl_out = p.second;
    insert_rf(ctrl_out, referent);
  }

  // Eliminate redundant RFs.
  bool progress = (redundant_rfs.size() > 0);
  while (redundant_rfs.size() > 0) {
    remove_rf(redundant_rfs.pop()->as_ReachabilityFence());
  }

  return progress;
}

//======================================================================
//---------------------------- Phase 2 ---------------------------------

// Linearly traverse CFG upwards starting at ctrl_start until first merge point.
// All encountered safepoints are recorded in safepoints list, except
// the ones filtered out by is_interfering_sfpt_candidate().
static void enumerate_interfering_sfpts_linear_traversal(Node* ctrl_start, Node_Stack& stack, VectorSet& visited,
                                                         Node_List& interfering_sfpts) {
  for (Node* ctrl = ctrl_start; ctrl != nullptr; ctrl = ctrl->in(0)) {
    assert(ctrl->is_CFG(), "");
    if (visited.test_set(ctrl->_idx)) {
      return;
    } else {
      if (ctrl->is_Region()) {
        stack.push(ctrl, 1);
        return; // stop at merge points
      } else if (ctrl->is_SafePoint() && is_interfering_sfpt_candidate(ctrl->as_SafePoint())) {
        assert(!ctrl->is_CallStaticJava() || !ctrl->as_CallStaticJava()->is_uncommon_trap(),
               "uncommon traps should not be enumerated");
        interfering_sfpts.push(ctrl);
      }
    }
  }
}

// Enumerate all safepoints which are reachable from the RF to its referent through CFG.
// Start at RF node and traverse CFG upwards until referent's control node is reached.
static void enumerate_interfering_sfpts(ReachabilityFenceNode* rf, PhaseIdealLoop* phase,
                                        Node_Stack& stack, VectorSet& visited,
                                        Node_List& interfering_sfpts) {
  assert(stack.is_empty(), "required");
  assert(visited.is_empty(), "required");

  Node* referent = rf->referent();
  Node* referent_ctrl = phase->get_ctrl(referent);
  assert(phase->is_dominator(referent_ctrl, rf), "sanity");

  visited.set(referent_ctrl->_idx); // end point
  enumerate_interfering_sfpts_linear_traversal(rf, stack, visited, interfering_sfpts); // starting point in CFG
  while (stack.is_nonempty()) {
    Node* cur = stack.node();
    uint  idx = stack.index();

    assert(cur != nullptr, "");
    assert(cur->is_Region(), "%s", NodeClassNames[cur->Opcode()]);
    assert(phase->is_dominator(referent_ctrl, cur), "");
    assert(idx > 0 && idx <= cur->req(), "%d %d", idx, cur->req());

    if (idx < cur->req()) {
      stack.set_index(idx + 1);
      enumerate_interfering_sfpts_linear_traversal(cur->in(idx), stack, visited, interfering_sfpts);
    } else {
      stack.pop();
    }
  }
  // Reset temporary structures to their initial state.
  assert(stack.is_empty(), "required");
  visited.clear();
}

// Start offset for reachability info on a safepoint node.
static uint rf_base_offset(SafePointNode* sfpt) {
  return sfpt->jvms()->debug_end();
}

static bool dominates_another_rf(ReachabilityFenceNode* rf, PhaseIdealLoop* phase) {
  assert(!rf->is_redundant(phase->igvn()), "");

  for (int i = 0; i < phase->C->reachability_fences_count(); i++) {
    ReachabilityFenceNode* other_rf = phase->C->reachability_fence(i);
    assert(other_rf->outcnt() > 0, "dead node");
    if (rf != other_rf && rf->referent()->eqv_uncast(other_rf->referent()) &&
        phase->is_dominator(rf, other_rf)) {
      return true; // dominates another reachability fence with the same referent
    }
  }
  return false;
}

// Phase 2: migrate reachability info to safepoints.
// All RFs are replaced with edges from corresponding referents to interfering safepoints.
// Interfering safepoints are safepoint nodes which are reachable from the RF to its referent through CFG.
bool PhaseIdealLoop::expand_reachability_fences() {
  Compile::TracePhase tp(_t_reachability_expand);

  assert(OptimizeReachabilityFences, "required");
  assert(C->post_loop_opts_phase(), "required");
  DEBUG_ONLY( int no_of_constant_rfs = 0; )

  ResourceMark rm;
  Unique_Node_List for_removal;
  typedef Pair<SafePointNode*,Node*> ReachabilityEdge;
  GrowableArray<ReachabilityEdge> reachability_edges;
  {
    // Reuse temporary structures to avoid allocating them for every single RF node.
    Node_List sfpt_worklist;
    Node_Stack stack(0);
    VectorSet visited;

    for (int i = 0; i < C->reachability_fences_count(); i++) {
      ReachabilityFenceNode* rf = C->reachability_fence(i);
      assert(!rf->is_redundant(igvn()), "missed");
      if (PreserveReachabilityFencesOnConstants) {
        const Type* referent_t = igvn().type(rf->referent());
        assert(referent_t != TypePtr::NULL_PTR, "redundant rf");
        bool is_constant_rf = referent_t->singleton();
        if (is_constant_rf) {
          DEBUG_ONLY( no_of_constant_rfs += 1; )
          continue; // leave RFs on constants intact
        }
      }
      if (dominates_another_rf(rf, this)) {
        // Redundant fence: dominates another RF with the same referent.
        // RF is redundant for some referent oop when the referent has another RF which
        // keeps it alive across the RF. In terms of dominance relation it can be formulated
        // as "a referent has another RF which is dominated by the redundant RF".
        //
        // NB! It is safe to assume that dominating RF is redundant only during expansion.
        // Otherwise, there's a chance for the superseding RF node to go away before expansion.
        // Non-RF users are ignored for a similar reason: they can go away before or after expansion
        // takes place, so no guarantees reachability information is preserved.
      } else {
        assert(sfpt_worklist.size() == 0, "not empty");
        enumerate_interfering_sfpts(rf, this, stack, visited, sfpt_worklist);

        Node* referent = rf->referent();
        while (sfpt_worklist.size() > 0) {
          SafePointNode* sfpt = sfpt_worklist.pop()->as_SafePoint();
          assert(is_dominator(get_ctrl(referent), sfpt), "");
          assert(sfpt->req() == rf_base_offset(sfpt), "no extra edges allowed");
          if (sfpt->find_edge(referent) == -1) {
            ReachabilityEdge p(sfpt, referent);
            reachability_edges.push(p);
          }
        }
      }
      for_removal.push(rf);
    }
  }
  // Materialize reachability edges.
  while (reachability_edges.length() > 0) {
    ReachabilityEdge p = reachability_edges.pop();
    SafePointNode* sfpt = p.first;
    Node* referent = p.second;
    if (sfpt->find_edge(referent) == -1) {
      sfpt->add_req(referent);
      igvn()._worklist.push(sfpt);
    }
  }
  // Eliminate processed RFs. They become redundant once reachability edges are added.
  bool progress = (for_removal.size() > 0);
  while (for_removal.size() > 0) {
    remove_rf(for_removal.pop()->as_ReachabilityFence());
  }

  assert(C->reachability_fences_count() == no_of_constant_rfs, "");
  return progress;
}

//======================================================================
//---------------------------- Phase 3 ---------------------------------

// Find a point in CFG right after safepoint node to insert reachability fence.
static Node* sfpt_ctrl_out(SafePointNode* sfpt) {
  if (sfpt->is_Call()) {
    CallProjections* callprojs = sfpt->as_Call()->extract_projections(false /*separate_io_proj*/,
                                                                      false /*do_asserts*/,
                                                                      true /*allow_handlers*/);
    // Calls can have multiple control projections. However, reachability edge expansion
    // happens during final graph reshaping which is performed very late in compilation pipeline.
    // The assumption here is that the control path chosen for insertion can't go away.
    // So, materializing a reachability fence on a single control path produced by a call
    // is enough to keep the referent oop alive across the call.
    if (callprojs->fallthrough_catchproj != nullptr) {
      return callprojs->fallthrough_catchproj;
    } else if (callprojs->catchall_catchproj != nullptr) {
      return callprojs->catchall_catchproj; // rethrow stub
    } else if (callprojs->fallthrough_proj != nullptr) {
      return callprojs->fallthrough_proj; // no exceptions thrown
    } else {
      ShouldNotReachHere();
    }
  } else {
    return sfpt;
  }
}

// Phase 3: materialize reachability fences from reachability edges on safepoints.
// Turn extra safepoint edges into reachability fences immediately following the safepoint.
//
// NB! As of now, a special care is needed to properly enumerate reachability edges because
// there are other use cases for non-debug safepoint edges. expand_reachability_edges() runs
// after macro expansion where runtime calls during array allocation are annotated with
// valid_length_test_input as an extra edges. Until there's a mechanism to distinguish between
// different types of non-debug edges, unrelated cases are filtered out explicitly and in ad-hoc manner.
void Compile::expand_reachability_edges(Unique_Node_List& safepoints) {
  for (uint i = 0; i < safepoints.size(); i++) {
    SafePointNode* sfpt = safepoints.at(i)->as_SafePoint();

    uint rf_offset = rf_base_offset(sfpt);
    if (sfpt->jvms() != nullptr && sfpt->req() > rf_offset) {
      assert(is_interfering_sfpt_candidate(sfpt), "");
      Node* ctrl_out = sfpt_ctrl_out(sfpt);
      Node* ctrl_end = ctrl_out->unique_ctrl_out();

      Node* extra_edge = nullptr;
      if (sfpt->is_Call()) {
        address entry = sfpt->as_Call()->entry_point();
        if (entry == OptoRuntime::new_array_Java() ||
            entry == OptoRuntime::new_array_nozero_Java()) {
          // valid_length_test_input is appended during macro expansion at the very end
          int last_idx = sfpt->req() - 1;
          extra_edge = sfpt->in(last_idx);
          sfpt->del_req(last_idx);
        }
      }

      while (sfpt->req() > rf_offset) {
        int idx = sfpt->req() - 1;
        Node* referent = sfpt->in(idx);
        sfpt->del_req(idx);

        Node* new_rf = new ReachabilityFenceNode(C, ctrl_out, referent);
        ctrl_end->replace_edge(ctrl_out, new_rf);
        ctrl_end = new_rf;
      }

      if (extra_edge != nullptr) {
        sfpt->add_req(extra_edge); // Add valid_length_test_input edge back
      }
    }
  }
}