Mercurial > jdk8-mips64-public > hotspot / file revision

 /*

  * Copyright (c) 1998, 2010, 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.

  *

  */

 #ifndef SHARE_VM_COMPILER_METHODLIVENESS_HPP

 #define SHARE_VM_COMPILER_METHODLIVENESS_HPP

 #include "utilities/bitMap.hpp"

 #include "utilities/growableArray.hpp"

 class ciMethod;

 class MethodLivenessResult : public BitMap {

  private:

   bool _is_valid;

  public:

   MethodLivenessResult(BitMap::bm_word_t* map, idx_t size_in_bits)

     : BitMap(map, size_in_bits)

     , _is_valid(false)

   {}

   MethodLivenessResult(idx_t size_in_bits)

     : BitMap(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;

     BitMap _entry;

     // The summarized liveness effects of our direct successors reached

     // by normal control flow

     BitMap _normal_exit;

     // The summarized liveness effects of our direct successors reached

     // by exceptional control flow

     BitMap _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.

     BitMap _gen;

     BitMap _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(BitMap other);

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

     // our _exception_exit member.

     bool merge_exception(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;

   int _bit_map_size_words;

   // 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

   BitMap _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; }

   int bit_map_size_words() const { return _bit_map_size_words; }

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

 };

 #endif // SHARE_VM_COMPILER_METHODLIVENESS_HPP