aoqi@0: /*
aoqi@0:  * Copyright (c) 1998, 2010, Oracle and/or its affiliates. All rights reserved.
aoqi@0:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
aoqi@0:  *
aoqi@0:  * This code is free software; you can redistribute it and/or modify it
aoqi@0:  * under the terms of the GNU General Public License version 2 only, as
aoqi@0:  * published by the Free Software Foundation.
aoqi@0:  *
aoqi@0:  * This code is distributed in the hope that it will be useful, but WITHOUT
aoqi@0:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
aoqi@0:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
aoqi@0:  * version 2 for more details (a copy is included in the LICENSE file that
aoqi@0:  * accompanied this code).
aoqi@0:  *
aoqi@0:  * You should have received a copy of the GNU General Public License version
aoqi@0:  * 2 along with this work; if not, write to the Free Software Foundation,
aoqi@0:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
aoqi@0:  *
aoqi@0:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
aoqi@0:  * or visit www.oracle.com if you need additional information or have any
aoqi@0:  * questions.
aoqi@0:  *
aoqi@0:  */
aoqi@0: 
aoqi@0: #ifndef SHARE_VM_COMPILER_METHODLIVENESS_HPP
aoqi@0: #define SHARE_VM_COMPILER_METHODLIVENESS_HPP
aoqi@0: 
aoqi@0: #include "utilities/bitMap.hpp"
aoqi@0: #include "utilities/growableArray.hpp"
aoqi@0: 
aoqi@0: class ciMethod;
aoqi@0: 
aoqi@0: class MethodLivenessResult : public BitMap {
aoqi@0:  private:
aoqi@0:   bool _is_valid;
aoqi@0: 
aoqi@0:  public:
aoqi@0:   MethodLivenessResult(BitMap::bm_word_t* map, idx_t size_in_bits)
aoqi@0:     : BitMap(map, size_in_bits)
aoqi@0:     , _is_valid(false)
aoqi@0:   {}
aoqi@0: 
aoqi@0:   MethodLivenessResult(idx_t size_in_bits)
aoqi@0:     : BitMap(size_in_bits)
aoqi@0:     , _is_valid(false)
aoqi@0:   {}
aoqi@0: 
aoqi@0:   void set_is_valid() { _is_valid = true; }
aoqi@0:   bool is_valid() { return _is_valid; }
aoqi@0: };
aoqi@0: 
aoqi@0: class MethodLiveness : public ResourceObj {
aoqi@0:  public:
aoqi@0:   // The BasicBlock class is used to represent a basic block in the
aoqi@0:   // liveness analysis.
aoqi@0:   class BasicBlock : public ResourceObj {
aoqi@0:    private:
aoqi@0:     // This class is only used by the MethodLiveness class.
aoqi@0:     friend class MethodLiveness;
aoqi@0: 
aoqi@0:     // The analyzer which created this basic block.
aoqi@0:     MethodLiveness* _analyzer;
aoqi@0: 
aoqi@0:     // The range of this basic block is [start_bci,limit_bci)
aoqi@0:     int _start_bci;
aoqi@0:     int _limit_bci;
aoqi@0: 
aoqi@0:     // The liveness at the start of the block;
aoqi@0:     BitMap _entry;
aoqi@0: 
aoqi@0:     // The summarized liveness effects of our direct successors reached
aoqi@0:     // by normal control flow
aoqi@0:     BitMap _normal_exit;
aoqi@0: 
aoqi@0:     // The summarized liveness effects of our direct successors reached
aoqi@0:     // by exceptional control flow
aoqi@0:     BitMap _exception_exit;
aoqi@0: 
aoqi@0:     // These members hold the results of the last call to
aoqi@0:     // compute_gen_kill_range().  _gen is the set of locals
aoqi@0:     // used before they are defined in the range.  _kill is the
aoqi@0:     // set of locals defined before they are used.
aoqi@0:     BitMap _gen;
aoqi@0:     BitMap _kill;
aoqi@0:     int    _last_bci;
aoqi@0: 
aoqi@0:     // A list of all blocks which could come directly before this one
aoqi@0:     // in normal (non-exceptional) control flow.  We propagate liveness
aoqi@0:     // information to these blocks.
aoqi@0:     GrowableArray<BasicBlock*>* _normal_predecessors;
aoqi@0: 
aoqi@0:     // A list of all blocks which could come directly before this one
aoqi@0:     // in exceptional control flow.
aoqi@0:     GrowableArray<BasicBlock*>* _exception_predecessors;
aoqi@0: 
aoqi@0:     // The following fields are used to manage a work list used in the
aoqi@0:     // dataflow.
aoqi@0:     BasicBlock *_next;
aoqi@0:     bool _on_work_list;
aoqi@0: 
aoqi@0:     // Our successors call this method to merge liveness information into
aoqi@0:     // our _normal_exit member.
aoqi@0:     bool merge_normal(BitMap other);
aoqi@0: 
aoqi@0:     // Our successors call this method to merge liveness information into
aoqi@0:     // our _exception_exit member.
aoqi@0:     bool merge_exception(BitMap other);
aoqi@0: 
aoqi@0:     // This helper routine is used to help compute the gen/kill pair for
aoqi@0:     // the block.  It is also used to answer queries.
aoqi@0:     void compute_gen_kill_range(ciBytecodeStream *bytes);
aoqi@0: 
aoqi@0:     // Compute the gen/kill effect of a single instruction.
aoqi@0:     void compute_gen_kill_single(ciBytecodeStream *instruction);
aoqi@0: 
aoqi@0:     // Helpers for compute_gen_kill_single.
aoqi@0:     void load_one(int local);
aoqi@0:     void load_two(int local);
aoqi@0:     void store_one(int local);
aoqi@0:     void store_two(int local);
aoqi@0: 
aoqi@0:     BasicBlock(MethodLiveness *analyzer, int start, int limit);
aoqi@0: 
aoqi@0:     // -- Accessors
aoqi@0: 
aoqi@0:     int start_bci() const { return _start_bci; }
aoqi@0: 
aoqi@0:     int limit_bci() const { return _limit_bci; }
aoqi@0:     void set_limit_bci(int limit) { _limit_bci = limit; }
aoqi@0: 
aoqi@0:     BasicBlock *next() const { return _next; }
aoqi@0:     void set_next(BasicBlock *next) { _next = next; }
aoqi@0: 
aoqi@0:     bool on_work_list() const { return _on_work_list; }
aoqi@0:     void set_on_work_list(bool val) { _on_work_list = val; }
aoqi@0: 
aoqi@0:     // -- Flow graph construction.
aoqi@0: 
aoqi@0:     // Add a basic block to our list of normal predecessors.
aoqi@0:     void add_normal_predecessor(BasicBlock *pred) {
aoqi@0:       _normal_predecessors->append_if_missing(pred);
aoqi@0:     }
aoqi@0: 
aoqi@0:     // Add a basic block to our list of exceptional predecessors
aoqi@0:     void add_exception_predecessor(BasicBlock *pred) {
aoqi@0:       _exception_predecessors->append_if_missing(pred);
aoqi@0:     }
aoqi@0: 
aoqi@0:     // Split the basic block at splitBci.  This basic block
aoqi@0:     // becomes the second half.  The first half is newly created.
aoqi@0:     BasicBlock *split(int splitBci);
aoqi@0: 
aoqi@0:     // -- Dataflow.
aoqi@0: 
aoqi@0:     void compute_gen_kill(ciMethod* method);
aoqi@0: 
aoqi@0:     // Propagate changes from this basic block
aoqi@0:     void propagate(MethodLiveness *ml);
aoqi@0: 
aoqi@0:     // -- Query.
aoqi@0: 
aoqi@0:     MethodLivenessResult get_liveness_at(ciMethod* method, int bci);
aoqi@0: 
aoqi@0:     // -- Debugging.
aoqi@0: 
aoqi@0:     void print_on(outputStream *os) const PRODUCT_RETURN;
aoqi@0: 
aoqi@0:   }; // End of MethodLiveness::BasicBlock
aoqi@0: 
aoqi@0:  private:
aoqi@0:   // The method we are analyzing.
aoqi@0:   ciMethod* _method;
aoqi@0:   ciMethod* method() const { return _method; }
aoqi@0: 
aoqi@0:   // The arena for storing structures...
aoqi@0:   Arena*       _arena;
aoqi@0:   Arena*       arena() const { return _arena; }
aoqi@0: 
aoqi@0:   // We cache the length of the method.
aoqi@0:   int _code_size;
aoqi@0: 
aoqi@0:   // The size of a BitMap.
aoqi@0:   int _bit_map_size_bits;
aoqi@0:   int _bit_map_size_words;
aoqi@0: 
aoqi@0:   // A list of all BasicBlocks.
aoqi@0:   BasicBlock **_block_list;
aoqi@0: 
aoqi@0:   // number of blocks
aoqi@0:   int  _block_count;
aoqi@0: 
aoqi@0:   // Keeps track of bci->block mapping.  One entry for each bci.  Only block starts are
aoqi@0:   // recorded.
aoqi@0:   GrowableArray<BasicBlock*>* _block_map;
aoqi@0: 
aoqi@0:   // Our work list.
aoqi@0:   BasicBlock *_work_list;
aoqi@0: 
aoqi@0: #ifdef COMPILER1
aoqi@0:   // bcis where blocks start are marked
aoqi@0:   BitMap _bci_block_start;
aoqi@0: #endif // COMPILER1
aoqi@0: 
aoqi@0:   // -- Graph construction & Analysis
aoqi@0: 
aoqi@0:   // Compute ranges and predecessors for basic blocks.
aoqi@0:   void init_basic_blocks();
aoqi@0: 
aoqi@0:   // Compute gen/kill information for all basic blocks.
aoqi@0:   void init_gen_kill();
aoqi@0: 
aoqi@0:   // Perform the dataflow.
aoqi@0:   void propagate_liveness();
aoqi@0: 
aoqi@0:  // The class MethodLiveness::BasicBlock needs special access to some
aoqi@0:  // of our members.
aoqi@0:  friend class MethodLiveness::BasicBlock;
aoqi@0: 
aoqi@0:   // And accessors.
aoqi@0:   int bit_map_size_bits() const { return _bit_map_size_bits; }
aoqi@0:   int bit_map_size_words() const { return _bit_map_size_words; }
aoqi@0: 
aoqi@0:   // Work list manipulation routines.  Called internally by BasicBlock.
aoqi@0:   BasicBlock *work_list_get();
aoqi@0:   void work_list_add(BasicBlock *block);
aoqi@0: 
aoqi@0:   // -- Timing and Statistics.
aoqi@0: 
aoqi@0: 
aoqi@0:   // Timers
aoqi@0:   static elapsedTimer _time_build_graph;
aoqi@0:   static elapsedTimer _time_gen_kill;
aoqi@0:   static elapsedTimer _time_flow;
aoqi@0:   static elapsedTimer _time_query;
aoqi@0:   static elapsedTimer _time_total;
aoqi@0: 
aoqi@0: #ifndef PRODUCT
aoqi@0: 
aoqi@0:   // Counts
aoqi@0:   static long _total_bytes;
aoqi@0:   static int  _total_methods;
aoqi@0: 
aoqi@0:   static long _total_blocks;
aoqi@0:   static int  _max_method_blocks;
aoqi@0: 
aoqi@0:   static long _total_edges;
aoqi@0:   static int  _max_block_edges;
aoqi@0: 
aoqi@0:   static long _total_exc_edges;
aoqi@0:   static int  _max_block_exc_edges;
aoqi@0: 
aoqi@0:   static long _total_method_locals;
aoqi@0:   static int  _max_method_locals;
aoqi@0: 
aoqi@0:   static long _total_locals_queried;
aoqi@0:   static long _total_live_locals_queried;
aoqi@0: 
aoqi@0:   static long _total_visits;
aoqi@0: 
aoqi@0: #endif
aoqi@0: 
aoqi@0:  public:
aoqi@0:   // Create a liveness analyzer for a method
aoqi@0:   MethodLiveness(Arena* arena, ciMethod* method);
aoqi@0: 
aoqi@0:   // Compute liveness information for the method
aoqi@0:   void compute_liveness();
aoqi@0: 
aoqi@0:   // Find out which locals are live at a specific bci.
aoqi@0:   MethodLivenessResult get_liveness_at(int bci);
aoqi@0: 
aoqi@0: #ifdef COMPILER1
aoqi@0:   const BitMap get_bci_block_start() const { return _bci_block_start; }
aoqi@0: #endif // COMPILER1
aoqi@0: 
aoqi@0:   static void print_times() PRODUCT_RETURN;
aoqi@0: };
aoqi@0: 
aoqi@0: #endif // SHARE_VM_COMPILER_METHODLIVENESS_HPP