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