/*

 * 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 "utilities/bitMap.hpp"

#include "utilities/growableArray.hpp"

class ciMethod;

class MethodLivenessResult : public ResourceBitMap {

 private:

  bool _is_valid;

 public:

  MethodLivenessResult()

    : ResourceBitMap()

    , _is_valid(false)

  {}

  MethodLivenessResult(idx_t size_in_bits)

    : ResourceBitMap(size_in_bits)

    , _is_valid(false)

  {}

  void set_is_valid() { _is_valid = true; }

  bool is_valid() { return _is_valid; }

};

class MethodLiveness : public ResourceObj {

 public:

  // The BasicBlock class is used to represent a basic block in the

  // liveness analysis.

  class BasicBlock : public ResourceObj {

   private:

    // This class is only used by the MethodLiveness class.

    friend class MethodLiveness;

    // The analyzer which created this basic block.

    MethodLiveness* _analyzer;

    // The range of this basic block is [start_bci,limit_bci)

    int _start_bci;

    int _limit_bci;

    // The liveness at the start of the block;

    ArenaBitMap _entry;

    // The summarized liveness effects of our direct successors reached

    // by normal control flow

    ArenaBitMap _normal_exit;

    // The summarized liveness effects of our direct successors reached

    // by exceptional control flow

    ArenaBitMap _exception_exit;

    // These members hold the results of the last call to

    // compute_gen_kill_range().  _gen is the set of locals

    // used before they are defined in the range.  _kill is the

    // set of locals defined before they are used.

    ArenaBitMap _gen;

    ArenaBitMap _kill;

    int         _last_bci;

    // A list of all blocks which could come directly before this one

    // in normal (non-exceptional) control flow.  We propagate liveness

    // information to these blocks.

    GrowableArray<BasicBlock*>* _normal_predecessors;

    // A list of all blocks which could come directly before this one

    // in exceptional control flow.

    GrowableArray<BasicBlock*>* _exception_predecessors;

    // The following fields are used to manage a work list used in the

    // dataflow.

    BasicBlock *_next;

    bool _on_work_list;

    // Our successors call this method to merge liveness information into

    // our _normal_exit member.

    bool merge_normal(const BitMap& other);

    // Our successors call this method to merge liveness information into

    // our _exception_exit member.

    bool merge_exception(const BitMap& other);

    // This helper routine is used to help compute the gen/kill pair for

    // the block.  It is also used to answer queries.

    void compute_gen_kill_range(ciBytecodeStream *bytes);

    // Compute the gen/kill effect of a single instruction.

    void compute_gen_kill_single(ciBytecodeStream *instruction);

    // Helpers for compute_gen_kill_single.

    void load_one(int local);

    void load_two(int local);

    void store_one(int local);

    void store_two(int local);

    BasicBlock(MethodLiveness *analyzer, int start, int limit);

    // -- Accessors

    int start_bci() const { return _start_bci; }

    int limit_bci() const { return _limit_bci; }

    void set_limit_bci(int limit) { _limit_bci = limit; }

    BasicBlock *next() const { return _next; }

    void set_next(BasicBlock *next) { _next = next; }

    bool on_work_list() const { return _on_work_list; }

    void set_on_work_list(bool val) { _on_work_list = val; }

    // -- Flow graph construction.

    // Add a basic block to our list of normal predecessors.

    void add_normal_predecessor(BasicBlock *pred) {

      _normal_predecessors->append_if_missing(pred);

    }

    // Add a basic block to our list of exceptional predecessors

    void add_exception_predecessor(BasicBlock *pred) {

      _exception_predecessors->append_if_missing(pred);

    }

    // Split the basic block at splitBci.  This basic block

    // becomes the second half.  The first half is newly created.

    BasicBlock *split(int splitBci);

    // -- Dataflow.

    void compute_gen_kill(ciMethod* method);

    // Propagate changes from this basic block

    void propagate(MethodLiveness *ml);

    // -- Query.

    MethodLivenessResult get_liveness_at(ciMethod* method, int bci);

    // -- Debugging.

    void print_on(outputStream *os) const PRODUCT_RETURN;

  }; // End of MethodLiveness::BasicBlock

 private:

  // The method we are analyzing.

  ciMethod* _method;

  ciMethod* method() const { return _method; }

  // The arena for storing structures...

  Arena*       _arena;

  Arena*       arena() const { return _arena; }

  // We cache the length of the method.

  int _code_size;

  // The size of a BitMap.

  int _bit_map_size_bits;

  // A list of all BasicBlocks.

  BasicBlock **_block_list;

  // number of blocks

  int  _block_count;

  // Keeps track of bci->block mapping.  One entry for each bci.  Only block starts are

  // recorded.

  GrowableArray<BasicBlock*>* _block_map;

  // Our work list.

  BasicBlock *_work_list;

#ifdef COMPILER1

  // bcis where blocks start are marked

  ArenaBitMap _bci_block_start;

#endif // COMPILER1

  // -- Graph construction & Analysis

  // Compute ranges and predecessors for basic blocks.

  void init_basic_blocks();

  // Compute gen/kill information for all basic blocks.

  void init_gen_kill();

  // Perform the dataflow.

  void propagate_liveness();

 // The class MethodLiveness::BasicBlock needs special access to some

 // of our members.

 friend class MethodLiveness::BasicBlock;

  // And accessors.

  int bit_map_size_bits() const { return _bit_map_size_bits; }

  // Work list manipulation routines.  Called internally by BasicBlock.

  BasicBlock *work_list_get();

  void work_list_add(BasicBlock *block);

  // -- Timing and Statistics.

  // Timers

  static elapsedTimer _time_build_graph;

  static elapsedTimer _time_gen_kill;

  static elapsedTimer _time_flow;

  static elapsedTimer _time_query;

  static elapsedTimer _time_total;

#ifndef PRODUCT

  // Counts

  static long _total_bytes;

  static int  _total_methods;

  static long _total_blocks;

  static int  _max_method_blocks;

  static long _total_edges;

  static int  _max_block_edges;

  static long _total_exc_edges;

  static int  _max_block_exc_edges;

  static long _total_method_locals;

  static int  _max_method_locals;

  static long _total_locals_queried;

  static long _total_live_locals_queried;

  static long _total_visits;

#endif

 public:

  // Create a liveness analyzer for a method

  MethodLiveness(Arena* arena, ciMethod* method);

  // Compute liveness information for the method

  void compute_liveness();

  // Find out which locals are live at a specific bci.

  MethodLivenessResult get_liveness_at(int bci);

#ifdef COMPILER1

  const BitMap& get_bci_block_start() const { return _bci_block_start; }

#endif // COMPILER1

  static void print_times() PRODUCT_RETURN;

};