/*

 * Copyright (c) 2001, 2005, 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.

 *

 */

package sun.jvm.hotspot.oops;

import java.io.*;

import java.util.*;

import sun.jvm.hotspot.interpreter.*;

import sun.jvm.hotspot.runtime.*;

import sun.jvm.hotspot.utilities.*;

/** Minimal port of the VM's oop map generator for interpreted frames */

public class GenerateOopMap {

  interface JumpClosure {

    public void process(GenerateOopMap c, int bcpDelta, int[] data);

  }

  // Used for debugging this code

  private static final boolean DEBUG = false;

  // These two should be removed. But requires som code to be cleaned up

  private static final int MAXARGSIZE     =   256;      // This should be enough

  private static final int MAX_LOCAL_VARS = 65536;      // 16-bit entry

  private static final boolean TraceMonitorMismatch = true;

  private static final boolean TraceOopMapRewrites = true;

  // Commonly used constants

  static CellTypeState[] epsilonCTS = { CellTypeState.bottom };

  static CellTypeState   refCTS     = CellTypeState.ref;

  static CellTypeState   valCTS     = CellTypeState.value;

  static CellTypeState[]    vCTS    = { CellTypeState.value, CellTypeState.bottom };

  static CellTypeState[]    rCTS    = { CellTypeState.ref,   CellTypeState.bottom };

  static CellTypeState[]   rrCTS    = { CellTypeState.ref,   CellTypeState.ref,   CellTypeState.bottom };

  static CellTypeState[]   vrCTS    = { CellTypeState.value, CellTypeState.ref,   CellTypeState.bottom };

  static CellTypeState[]   vvCTS    = { CellTypeState.value, CellTypeState.value, CellTypeState.bottom };

  static CellTypeState[]  rvrCTS    = { CellTypeState.ref,   CellTypeState.value, CellTypeState.ref,   CellTypeState.bottom };

  static CellTypeState[]  vvrCTS    = { CellTypeState.value, CellTypeState.value, CellTypeState.ref,   CellTypeState.bottom };

  static CellTypeState[]  vvvCTS    = { CellTypeState.value, CellTypeState.value, CellTypeState.value, CellTypeState.bottom };

  static CellTypeState[] vvvrCTS    = { CellTypeState.value, CellTypeState.value, CellTypeState.value, CellTypeState.ref,   CellTypeState.bottom };

  static CellTypeState[] vvvvCTS    = { CellTypeState.value, CellTypeState.value, CellTypeState.value, CellTypeState.value, CellTypeState.bottom };

  /** Specialization of SignatureIterator - compute the effects of a call */

  static class ComputeCallStack extends SignatureIterator {

    CellTypeStateList _effect;

    int _idx;

    void set(CellTypeState state)         { _effect.get(_idx++).set(state); }

    int  length()                         { return _idx; };

    public void doBool  ()              { set(CellTypeState.value); }

    public void doChar  ()              { set(CellTypeState.value); }

    public void doFloat ()              { set(CellTypeState.value); }

    public void doByte  ()              { set(CellTypeState.value); }

    public void doShort ()              { set(CellTypeState.value); }

    public void doInt   ()              { set(CellTypeState.value); }

    public void doVoid  ()              { set(CellTypeState.bottom);}

    public void doObject(int begin, int end) { set(CellTypeState.ref); }

    public void doArray (int begin, int end) { set(CellTypeState.ref); }

    public void doDouble()              { set(CellTypeState.value);

                                          set(CellTypeState.value); }

    public void doLong  ()              { set(CellTypeState.value);

                                          set(CellTypeState.value); }

    ComputeCallStack(Symbol signature) {

      super(signature);

    }

    // Compute methods

    int computeForParameters(boolean is_static, CellTypeStateList effect) {

      _idx    = 0;

      _effect = effect;

      if (!is_static) {

        effect.get(_idx++).set(CellTypeState.ref);

      }

      iterateParameters();

      return length();

    };

    int computeForReturntype(CellTypeStateList effect) {

      _idx    = 0;

      _effect = effect;

      iterateReturntype();

      set(CellTypeState.bottom);  // Always terminate with a bottom state, so ppush works

      return length();

    }

  }

  /** Specialization of SignatureIterator - in order to set up first stack frame */

  static class ComputeEntryStack extends SignatureIterator {

    CellTypeStateList _effect;

    int _idx;

    void set(CellTypeState state)         { _effect.get(_idx++).set(state); }

    int  length()                         { return _idx; };

    public void doBool  ()              { set(CellTypeState.value); }

    public void doChar  ()              { set(CellTypeState.value); }

    public void doFloat ()              { set(CellTypeState.value); }

    public void doByte  ()              { set(CellTypeState.value); }

    public void doShort ()              { set(CellTypeState.value); }

    public void doInt   ()              { set(CellTypeState.value); }

    public void doVoid  ()              { set(CellTypeState.bottom);}

    public void doObject(int begin, int end) { set(CellTypeState.makeSlotRef(_idx)); }

    public void doArray (int begin, int end) { set(CellTypeState.makeSlotRef(_idx)); }

    public void doDouble()              { set(CellTypeState.value);

                                          set(CellTypeState.value); }

    public void doLong  ()              { set(CellTypeState.value);

                                          set(CellTypeState.value); }

    ComputeEntryStack(Symbol signature) {

      super(signature);

    }

    // Compute methods

    int computeForParameters(boolean is_static, CellTypeStateList effect) {

      _idx    = 0;

      _effect = effect;

      if (!is_static) {

        effect.get(_idx++).set(CellTypeState.makeSlotRef(0));

      }

      iterateParameters();

      return length();

    };

    int computeForReturntype(CellTypeStateList effect) {

      _idx    = 0;

      _effect = effect;

      iterateReturntype();

      set(CellTypeState.bottom);  // Always terminate with a bottom state, so ppush works

      return length();

    }

  }

  /** Contains maping between jsr targets and there return addresses.

      One-to-many mapping. */

  static class RetTableEntry {

    private static int _init_nof_jsrs; // Default size of jsrs list

    private int _target_bci;           // Target PC address of jump (bytecode index)

    private List/*<int>*/ _jsrs;       // List of return addresses  (bytecode index)

    private RetTableEntry _next;       // Link to next entry

    RetTableEntry(int target, RetTableEntry next) {

      _target_bci = target;

      _jsrs = new ArrayList(_init_nof_jsrs);

      _next = next;

    }

    // Query

    int targetBci()  { return _target_bci; }

    int nofJsrs()    { return _jsrs.size(); }

    int jsrs(int i)  { return ((Integer) _jsrs.get(i)).intValue(); }

    // Update entry

    void addJsr  (int return_bci)     { _jsrs.add(new Integer(return_bci)); }

    void addDelta(int bci, int delta) {

      if (_target_bci > bci) {

        _target_bci += delta;

      }

      for (int k = 0; k < nofJsrs(); k++) {

        int jsr = jsrs(k);

        if (jsr > bci) {

          _jsrs.set(k, new Integer(jsr+delta));

        }

      }

    }

    RetTableEntry next()               { return _next; }

  }

  static class RetTable {

    private RetTableEntry _first;

    private static int _init_nof_entries;

    private void addJsr(int return_bci, int target_bci) {

      RetTableEntry entry = _first;

      // Scan table for entry

      for (;(entry != null) && (entry.targetBci() != target_bci); entry = entry.next());

      if (entry == null) {

        // Allocate new entry and put in list

        entry = new RetTableEntry(target_bci, _first);

        _first = entry;

      }

      // Now "entry" is set.  Make sure that the entry is initialized

      // and has room for the new jsr.

      entry.addJsr(return_bci);

    }

    RetTable() {}

    void computeRetTable(Method method) {

      BytecodeStream i = new BytecodeStream(method);

      int bytecode;

      while( (bytecode = i.next()) >= 0) {

        switch (bytecode) {

        case Bytecodes._jsr:

          addJsr(i.nextBCI(), i.dest());

          break;

        case Bytecodes._jsr_w:

          addJsr(i.nextBCI(), i.dest_w());

          break;

        }

      }

    }

    void updateRetTable(int bci, int delta) {

      RetTableEntry cur = _first;

      while(cur != null) {

        cur.addDelta(bci, delta);

        cur = cur.next();

      }

    }

    RetTableEntry findJsrsForTarget(int targBci) {

      RetTableEntry cur = _first;

      while(cur != null) {

        if (Assert.ASSERTS_ENABLED) {

          Assert.that(cur.targetBci() != -1, "sanity check");

        }

        if (cur.targetBci() == targBci) {

          return cur;

        }

        cur = cur.next();

      }

      throw new RuntimeException("Should not reach here");

    }

  }

  static class BasicBlock {

    private boolean _changed;              // Reached a fixpoint or not

    static final int _dead_basic_block = -2;

    // Alive but not yet reached by analysis

    static final int _unreached        = -1;

    // >=0: Alive and has a merged state

    int                     _bci;          // Start of basic block

    int                     _end_bci;      // Bci of last instruction in basicblock

    int                     _max_locals;   // Determines split between vars and stack

    int                     _max_stack;    // Determines split between stack and monitors

    CellTypeStateList       _state;        // State (vars, stack) at entry.

    int                     _stack_top;    // -1 indicates bottom stack value.

    int                     _monitor_top;  // -1 indicates bottom monitor stack value.

    CellTypeStateList       vars()  { return _state; }

    CellTypeStateList       stack() { return _state.subList(_max_locals, _state.size()); }

    boolean changed()               { return _changed; }

    void    setChanged(boolean s)   { _changed = s; }

    // Analysis has reached this basicblock

    boolean isReachable()           { return _stack_top >= 0; }

    // All basicblocks that are unreachable are going to have a _stack_top == _dead_basic_block.

    // This info. is setup in a pre-parse before the real abstract interpretation starts.

    boolean isDead()                { return _stack_top == _dead_basic_block; }

    boolean isAlive()               { return _stack_top != _dead_basic_block; }

    void    markAsAlive()           {

      if (Assert.ASSERTS_ENABLED) {

        Assert.that(isDead(), "must be dead");

        _stack_top = _unreached;

      }

    }

  }

  //----------------------------------------------------------------------

  // Protected routines for GenerateOopMap

  //

  // _monitor_top is set to this constant to indicate that a monitor matching

  // problem was encountered prior to this point in control flow.

  protected static final int bad_monitors = -1;

  // Main variables

  Method   _method;         // The method we are examining

  RetTable _rt;             // Contains the return address mappings

  int      _max_locals;     // Cached value of no. of locals

  int      _max_stack;      // Cached value of max. stack depth

  int      _max_monitors;   // Cached value of max. monitor stack depth

  boolean  _has_exceptions; // True, if exceptions exist for method

  boolean  _got_error;      // True, if an error occured during interpretation.

  String   _error_msg;      // Error message. Set if _got_error is true.

  //  bool     _did_rewriting;  // was bytecodes rewritten

  //  bool     _did_relocation; // was relocation neccessary

  boolean  _monitor_safe;   // The monitors in this method have been determined

                            // to be safe.

  // Working Cell type state

  int               _state_len;     // Size of states

  CellTypeStateList _state;         // list of states

  char[]            _state_vec_buf; // Buffer used to print a readable version of a state

  int               _stack_top;

  int               _monitor_top;

  // Timing and statistics

  //  static elapsedTimer _total_oopmap_time;   // Holds cumulative oopmap generation time

  //  static long         _total_byte_count;    // Holds cumulative number of bytes inspected

  // Monitor query logic

  int _report_for_exit_bci;

  int _matching_enter_bci;

  // Cell type methods

  void            initState() {

    _state_len = _max_locals + _max_stack + _max_monitors;

    _state     = new CellTypeStateList(_state_len);

    _state_vec_buf = new char[Math.max(_max_locals, Math.max(_max_stack, Math.max(_max_monitors, 1)))];

  }

  void            makeContextUninitialized () {

    CellTypeStateList vs = vars();

    for (int i = 0; i < _max_locals; i++)

      vs.get(i).set(CellTypeState.uninit);

    _stack_top = 0;

    _monitor_top = 0;

  }

  int             methodsigToEffect          (Symbol signature, boolean isStatic, CellTypeStateList effect) {

    ComputeEntryStack ces = new ComputeEntryStack(signature);

    return ces.computeForParameters(isStatic, effect);

  }

  boolean         mergeStateVectors          (CellTypeStateList cts, CellTypeStateList bbts) {

    int i;

    int len = _max_locals + _stack_top;

    boolean change = false;

    for (i = len - 1; i >= 0; i--) {

      CellTypeState v = cts.get(i).merge(bbts.get(i), i);

      change = change || !v.equal(bbts.get(i));

      bbts.get(i).set(v);

    }

    if (_max_monitors > 0 && _monitor_top != bad_monitors) {

      // If there are no monitors in the program, or there has been

      // a monitor matching error before this point in the program,

      // then we do not merge in the monitor state.

      int base = _max_locals + _max_stack;

      len = base + _monitor_top;

      for (i = len - 1; i >= base; i--) {

        CellTypeState v = cts.get(i).merge(bbts.get(i), i);

        // Can we prove that, when there has been a change, it will already

        // have been detected at this point?  That would make this equal

        // check here unnecessary.

        change = change || !v.equal(bbts.get(i));

        bbts.get(i).set(v);

      }

    }

    return change;

  }

  void            copyState                  (CellTypeStateList dst, CellTypeStateList src) {

    int len = _max_locals + _stack_top;

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

      if (src.get(i).isNonlockReference()) {

        dst.get(i).set(CellTypeState.makeSlotRef(i));

      } else {

        dst.get(i).set(src.get(i));

      }

    }

    if (_max_monitors > 0 && _monitor_top != bad_monitors) {

      int base = _max_locals + _max_stack;

      len = base + _monitor_top;

      for (int i = base; i < len; i++) {

        dst.get(i).set(src.get(i));

      }

    }

  }

  void            mergeStateIntoBB           (BasicBlock bb) {

    if (Assert.ASSERTS_ENABLED) {

      Assert.that(bb.isAlive(), "merging state into a dead basicblock");

    }

    if (_stack_top == bb._stack_top) {

      if (_monitor_top == bb._monitor_top) {

        if (mergeStateVectors(_state, bb._state)) {

          bb.setChanged(true);

        }

      } else {

        if (TraceMonitorMismatch) {

          reportMonitorMismatch("monitor stack height merge conflict");

        }

        // When the monitor stacks are not matched, we set _monitor_top to

        // bad_monitors.  This signals that, from here on, the monitor stack cannot

        // be trusted.  In particular, monitorexit bytecodes may throw

        // exceptions.  We mark this block as changed so that the change

        // propagates properly.

        bb._monitor_top = bad_monitors;

        bb.setChanged(true);

        _monitor_safe = false;

      }

    } else if (!bb.isReachable()) {

      // First time we look at this  BB

      copyState(bb._state, _state);

      bb._stack_top = _stack_top;

      bb._monitor_top = _monitor_top;

      bb.setChanged(true);

    } else {

      throw new RuntimeException("stack height conflict: " +

                                 _stack_top + " vs. " + bb._stack_top);

    }

  }

  void            mergeState                 (int bci, int[] data) {

    mergeStateIntoBB(getBasicBlockAt(bci));

  }

  void            setVar                     (int localNo, CellTypeState cts) {

    if (Assert.ASSERTS_ENABLED) {

      Assert.that(cts.isReference() || cts.isValue() || cts.isAddress(),

                  "wrong celltypestate");

    }

    if (localNo < 0 || localNo > _max_locals) {

      throw new RuntimeException("variable write error: r" + localNo);

    }

    vars().get(localNo).set(cts);

  }

  CellTypeState   getVar                     (int localNo) {

    if (Assert.ASSERTS_ENABLED) {

      Assert.that(localNo < _max_locals + _nof_refval_conflicts, "variable read error");

    }

    if (localNo < 0 || localNo > _max_locals) {

      throw new RuntimeException("variable read error: r" + localNo);

    }

    return vars().get(localNo).copy();

  }

  CellTypeState   pop                        () {

    if ( _stack_top <= 0) {

      throw new RuntimeException("stack underflow");

    }

    return  stack().get(--_stack_top).copy();

  }

  void            push                       (CellTypeState cts) {

    if ( _stack_top >= _max_stack) {

      if (DEBUG) {

        System.err.println("Method: " + method().getName().asString() + method().getSignature().asString() +

                           " _stack_top: " + _stack_top + " _max_stack: " + _max_stack);

      }

      throw new RuntimeException("stack overflow");

    }

    stack().get(_stack_top++).set(cts);

    if (DEBUG) {

      System.err.println("After push: _stack_top: " + _stack_top +

                         " _max_stack: " + _max_stack +

                         " just pushed: " + cts.toChar());

    }

  }

  CellTypeState   monitorPop                 () {

    if (Assert.ASSERTS_ENABLED) {

      Assert.that(_monitor_top != bad_monitors, "monitorPop called on error monitor stack");

    }

    if (_monitor_top == 0) {

      // We have detected a pop of an empty monitor stack.

      _monitor_safe = false;

      _monitor_top = bad_monitors;

      if (TraceMonitorMismatch) {

        reportMonitorMismatch("monitor stack underflow");

      }

      return CellTypeState.ref; // just to keep the analysis going.

    }

    return  monitors().get(--_monitor_top).copy();

  }

  void            monitorPush                (CellTypeState cts) {

    if (Assert.ASSERTS_ENABLED) {

      Assert.that(_monitor_top != bad_monitors, "monitorPush called on error monitor stack");

    }

    if (_monitor_top >= _max_monitors) {

      // Some monitorenter is being executed more than once.

      // This means that the monitor stack cannot be simulated.

      _monitor_safe = false;

      _monitor_top = bad_monitors;

      if (TraceMonitorMismatch) {

        reportMonitorMismatch("monitor stack overflow");

      }

      return;

    }

    monitors().get(_monitor_top++).set(cts);

  }

  CellTypeStateList vars    ()     { return _state; }

  CellTypeStateList stack   ()     { return _state.subList(_max_locals, _state.size()); }

  CellTypeStateList monitors()     { return _state.subList(_max_locals+_max_stack, _state.size()); }

  void            replaceAllCTSMatches       (CellTypeState match,