1 /*

     2  * Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.

     8  *

     9  * This code is distributed in the hope that it will be useful, but WITHOUT

    10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    12  * version 2 for more details (a copy is included in the LICENSE file that

    13  * accompanied this code).

    14  *

    15  * You should have received a copy of the GNU General Public License version

    16  * 2 along with this work; if not, write to the Free Software Foundation,

    17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    18  *

    19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    20  * or visit www.oracle.com if you need additional information or have any

    21  * questions.

    22  *

    23  */

    24 

    25 #ifndef SHARE_VM_COMPILER_METHODLIVENESS_HPP

    26 #define SHARE_VM_COMPILER_METHODLIVENESS_HPP

    27 

    28 #include "utilities/bitMap.hpp"

    29 #include "utilities/growableArray.hpp"

    30 

    31 class ciMethod;

    32 

    33 class MethodLivenessResult : public ResourceBitMap {

    34  private:

    35   bool _is_valid;

    36 

    37  public:

    38   MethodLivenessResult()

    39     : ResourceBitMap()

    40     , _is_valid(false)

    41   {}

    42 

    43   MethodLivenessResult(idx_t size_in_bits)

    44     : ResourceBitMap(size_in_bits)

    45     , _is_valid(false)

    46   {}

    47 

    48   void set_is_valid() { _is_valid = true; }

    49   bool is_valid() { return _is_valid; }

    50 };

    51 

    52 class MethodLiveness : public ResourceObj {

    53  public:

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

    55   // liveness analysis.

    56   class BasicBlock : public ResourceObj {

    57    private:

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

    59     friend class MethodLiveness;

    60 

    61     // The analyzer which created this basic block.

    62     MethodLiveness* _analyzer;

    63 

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

    65     int _start_bci;

    66     int _limit_bci;

    67 

    68     // The liveness at the start of the block;

    69     ArenaBitMap _entry;

    70 

    71     // The summarized liveness effects of our direct successors reached

    72     // by normal control flow

    73     ArenaBitMap _normal_exit;

    74 

    75     // The summarized liveness effects of our direct successors reached

    76     // by exceptional control flow

    77     ArenaBitMap _exception_exit;

    78 

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

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

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

    82     // set of locals defined before they are used.

    83     ArenaBitMap _gen;

    84     ArenaBitMap _kill;

    85     int         _last_bci;

    86 

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

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

    89     // information to these blocks.

    90     GrowableArray<BasicBlock*>* _normal_predecessors;

    91 

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

    93     // in exceptional control flow.

    94     GrowableArray<BasicBlock*>* _exception_predecessors;

    95 

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

    97     // dataflow.

    98     BasicBlock *_next;

    99     bool _on_work_list;

   100 

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

   102     // our _normal_exit member.

   103     bool merge_normal(const BitMap& other);

   104 

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

   106     // our _exception_exit member.

   107     bool merge_exception(const BitMap& other);

   108 

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

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

   111     void compute_gen_kill_range(ciBytecodeStream *bytes);

   112 

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

   114     void compute_gen_kill_single(ciBytecodeStream *instruction);

   115 

   116     // Helpers for compute_gen_kill_single.

   117     void load_one(int local);

   118     void load_two(int local);

   119     void store_one(int local);

   120     void store_two(int local);

   121 

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

   123 

   124     // -- Accessors

   125 

   126     int start_bci() const { return _start_bci; }

   127 

   128     int limit_bci() const { return _limit_bci; }

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

   130 

   131     BasicBlock *next() const { return _next; }

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

   133 

   134     bool on_work_list() const { return _on_work_list; }

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

   136 

   137     // -- Flow graph construction.

   138 

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

   140     void add_normal_predecessor(BasicBlock *pred) {

   141       _normal_predecessors->append_if_missing(pred);

   142     }

   143 

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

   145     void add_exception_predecessor(BasicBlock *pred) {

   146       _exception_predecessors->append_if_missing(pred);

   147     }

   148 

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

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

   151     BasicBlock *split(int splitBci);

   152 

   153     // -- Dataflow.

   154 

   155     void compute_gen_kill(ciMethod* method);

   156 

   157     // Propagate changes from this basic block

   158     void propagate(MethodLiveness *ml);

   159 

   160     // -- Query.

   161 

   162     MethodLivenessResult get_liveness_at(ciMethod* method, int bci);

   163 

   164     // -- Debugging.

   165 

   166     void print_on(outputStream *os) const PRODUCT_RETURN;

   167 

   168   }; // End of MethodLiveness::BasicBlock

   169 

   170  private:

   171   // The method we are analyzing.

   172   ciMethod* _method;

   173   ciMethod* method() const { return _method; }

   174 

   175   // The arena for storing structures...

   176   Arena*       _arena;

   177   Arena*       arena() const { return _arena; }

   178 

   179   // We cache the length of the method.

   180   int _code_size;

   181 

   182   // The size of a BitMap.

   183   int _bit_map_size_bits;

   184 

   185   // A list of all BasicBlocks.

   186   BasicBlock **_block_list;

   187 

   188   // number of blocks

   189   int  _block_count;

   190 

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

   192   // recorded.

   193   GrowableArray<BasicBlock*>* _block_map;

   194 

   195   // Our work list.

   196   BasicBlock *_work_list;

   197 

   198 #ifdef COMPILER1

   199   // bcis where blocks start are marked

   200   ArenaBitMap _bci_block_start;

   201 #endif // COMPILER1

   202 

   203   // -- Graph construction & Analysis

   204 

   205   // Compute ranges and predecessors for basic blocks.

   206   void init_basic_blocks();

   207 

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

   209   void init_gen_kill();

   210 

   211   // Perform the dataflow.

   212   void propagate_liveness();

   213 

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

   215  // of our members.

   216  friend class MethodLiveness::BasicBlock;

   217 

   218   // And accessors.

   219   int bit_map_size_bits() const { return _bit_map_size_bits; }

   220 

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

   222   BasicBlock *work_list_get();

   223   void work_list_add(BasicBlock *block);

   224 

   225   // -- Timing and Statistics.

   226 

   227 

   228   // Timers

   229   static elapsedTimer _time_build_graph;

   230   static elapsedTimer _time_gen_kill;

   231   static elapsedTimer _time_flow;

   232   static elapsedTimer _time_query;

   233   static elapsedTimer _time_total;

   234 

   235 #ifndef PRODUCT

   236 

   237   // Counts

   238   static long _total_bytes;

   239   static int  _total_methods;

   240 

   241   static long _total_blocks;

   242   static int  _max_method_blocks;

   243 

   244   static long _total_edges;

   245   static int  _max_block_edges;

   246 

   247   static long _total_exc_edges;

   248   static int  _max_block_exc_edges;

   249 

   250   static long _total_method_locals;

   251   static int  _max_method_locals;

   252 

   253   static long _total_locals_queried;

   254   static long _total_live_locals_queried;

   255 

   256   static long _total_visits;

   257 

   258 #endif

   259 

   260  public:

   261   // Create a liveness analyzer for a method

   262   MethodLiveness(Arena* arena, ciMethod* method);

   263 

   264   // Compute liveness information for the method

   265   void compute_liveness();

   266 

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

   268   MethodLivenessResult get_liveness_at(int bci);

   269 

   270 #ifdef COMPILER1

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

   272 #endif // COMPILER1

   273 

   274   static void print_times() PRODUCT_RETURN;

   275 };

   276 

   277 #endif // SHARE_VM_COMPILER_METHODLIVENESS_HPP