1 #ifdef USE_PRAGMA_IDENT_HDR
   2 #pragma ident "@(#)methodLiveness.hpp   1.25 07/05/05 17:05:24 JVM"
   3 #endif
   4 /*
   5  * Copyright 1998-2006 Sun Microsystems, Inc.  All Rights Reserved.
   6  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   7  *
   8  * This code is free software; you can redistribute it and/or modify it
   9  * under the terms of the GNU General Public License version 2 only, as
  10  * published by the Free Software Foundation.
  11  *
  12  * This code is distributed in the hope that it will be useful, but WITHOUT
  13  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15  * version 2 for more details (a copy is included in the LICENSE file that
  16  * accompanied this code).
  17  *
  18  * You should have received a copy of the GNU General Public License version
  19  * 2 along with this work; if not, write to the Free Software Foundation,
  20  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  21  *
  22  * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
  23  * CA 95054 USA or visit www.sun.com if you need additional information or
  24  * have any questions.
  25  *  
  26  */
  27 
  28 class ciMethod;
  29 
  30 class MethodLivenessResult : public BitMap {
  31  private:
  32   bool _is_valid;
  33 
  34  public:
  35   MethodLivenessResult(BitMap::bm_word_t* map, idx_t size_in_bits)
  36     : BitMap(map, size_in_bits)
  37     , _is_valid(false)
  38   {}
  39 
  40   MethodLivenessResult(idx_t size_in_bits)
  41     : BitMap(size_in_bits)
  42     , _is_valid(false)
  43   {}
  44 
  45   void set_is_valid() { _is_valid = true; }
  46   bool is_valid() { return _is_valid; }
  47 };
  48 
  49 class MethodLiveness : public ResourceObj {
  50  public: 
  51   // The BasicBlock class is used to represent a basic block in the
  52   // liveness analysis.
  53   class BasicBlock : public ResourceObj {
  54    private:
  55     // This class is only used by the MethodLiveness class.
  56     friend class MethodLiveness;
  57 
  58     // The analyzer which created this basic block.
  59     MethodLiveness* _analyzer;
  60     
  61     // The range of this basic block is [start_bci,limit_bci)
  62     int _start_bci;
  63     int _limit_bci;
  64 
  65     // The liveness at the start of the block;
  66     BitMap _entry;
  67 
  68     // The summarized liveness effects of our direct successors reached
  69     // by normal control flow
  70     BitMap _normal_exit;
  71 
  72     // The summarized liveness effects of our direct successors reached
  73     // by exceptional control flow
  74     BitMap _exception_exit;
  75 
  76     // These members hold the results of the last call to 
  77     // compute_gen_kill_range().  _gen is the set of locals
  78     // used before they are defined in the range.  _kill is the
  79     // set of locals defined before they are used.
  80     BitMap _gen;
  81     BitMap _kill;
  82     int    _last_bci;
  83 
  84     // A list of all blocks which could come directly before this one
  85     // in normal (non-exceptional) control flow.  We propagate liveness
  86     // information to these blocks.
  87     GrowableArray<BasicBlock*>* _normal_predecessors;
  88     
  89     // A list of all blocks which could come directly before this one
  90     // in exceptional control flow.
  91     GrowableArray<BasicBlock*>* _exception_predecessors;
  92 
  93     // The following fields are used to manage a work list used in the
  94     // dataflow.
  95     BasicBlock *_next;
  96     bool _on_work_list;
  97 
  98     // Our successors call this method to merge liveness information into
  99     // our _normal_exit member.
 100     bool merge_normal(BitMap other);
 101 
 102     // Our successors call this method to merge liveness information into
 103     // our _exception_exit member.
 104     bool merge_exception(BitMap other);
 105 
 106     // This helper routine is used to help compute the gen/kill pair for
 107     // the block.  It is also used to answer queries.
 108     void compute_gen_kill_range(ciBytecodeStream *bytes);
 109 
 110     // Compute the gen/kill effect of a single instruction.
 111     void compute_gen_kill_single(ciBytecodeStream *instruction);
 112 
 113     // Helpers for compute_gen_kill_single.
 114     void load_one(int local);
 115     void load_two(int local);
 116     void store_one(int local);
 117     void store_two(int local);
 118 
 119     BasicBlock(MethodLiveness *analyzer, int start, int limit);
 120 
 121     // -- Accessors
 122 
 123     int start_bci() const { return _start_bci; }
 124 
 125     int limit_bci() const { return _limit_bci; }
 126     void set_limit_bci(int limit) { _limit_bci = limit; } 
 127 
 128     BasicBlock *next() const { return _next; }
 129     void set_next(BasicBlock *next) { _next = next; }
 130 
 131     bool on_work_list() const { return _on_work_list; }
 132     void set_on_work_list(bool val) { _on_work_list = val; }
 133 
 134     // -- Flow graph construction.
 135 
 136     // Add a basic block to our list of normal predecessors.
 137     void add_normal_predecessor(BasicBlock *pred) {
 138       _normal_predecessors->append_if_missing(pred);
 139     }
 140 
 141     // Add a basic block to our list of exceptional predecessors
 142     void add_exception_predecessor(BasicBlock *pred) {
 143       _exception_predecessors->append_if_missing(pred);
 144     }
 145 
 146     // Split the basic block at splitBci.  This basic block
 147     // becomes the second half.  The first half is newly created.
 148     BasicBlock *split(int splitBci);
 149 
 150     // -- Dataflow.
 151     
 152     void compute_gen_kill(ciMethod* method);
 153 
 154     // Propagate changes from this basic block
 155     void propagate(MethodLiveness *ml);
 156 
 157     // -- Query.
 158 
 159     MethodLivenessResult get_liveness_at(ciMethod* method, int bci);
 160 
 161     // -- Debugging.
 162 
 163     void print_on(outputStream *os) const PRODUCT_RETURN;
 164 
 165   }; // End of MethodLiveness::BasicBlock
 166 
 167  private:
 168   // The method we are analyzing.
 169   ciMethod* _method;
 170   ciMethod* method() const { return _method; }
 171 
 172   // The arena for storing structures...
 173   Arena*       _arena;
 174   Arena*       arena() const { return _arena; }
 175 
 176   // We cache the length of the method.
 177   int _code_size;
 178 
 179   // The size of a BitMap.
 180   int _bit_map_size_bits;
 181   int _bit_map_size_words;
 182 
 183   // A list of all BasicBlocks.
 184   BasicBlock **_block_list;
 185 
 186   // number of blocks
 187   int  _block_count;
 188 
 189   // Keeps track of bci->block mapping.  One entry for each bci.  Only block starts are
 190   // recorded.
 191   GrowableArray<BasicBlock*>* _block_map;
 192 
 193   // Our work list.
 194   BasicBlock *_work_list;
 195 
 196 #ifdef COMPILER1
 197   // bcis where blocks start are marked
 198   BitMap _bci_block_start;
 199 #endif // COMPILER1
 200 
 201   // -- Graph construction & Analysis
 202 
 203   // Compute ranges and predecessors for basic blocks.
 204   void init_basic_blocks();
 205 
 206   // Compute gen/kill information for all basic blocks.
 207   void init_gen_kill();
 208 
 209   // Perform the dataflow.
 210   void propagate_liveness();
 211 
 212  // The class MethodLiveness::BasicBlock needs special access to some
 213  // of our members.
 214  friend class MethodLiveness::BasicBlock;
 215 
 216   // And accessors.
 217   int bit_map_size_bits() const { return _bit_map_size_bits; }
 218   int bit_map_size_words() const { return _bit_map_size_words; }
 219 
 220   // Work list manipulation routines.  Called internally by BasicBlock.
 221   BasicBlock *work_list_get();
 222   void work_list_add(BasicBlock *block);
 223 
 224   // -- Timing and Statistics.
 225 
 226 
 227   // Timers
 228   static elapsedTimer _time_build_graph;
 229   static elapsedTimer _time_gen_kill;
 230   static elapsedTimer _time_flow;
 231   static elapsedTimer _time_query;
 232   static elapsedTimer _time_total;
 233 
 234 #ifndef PRODUCT
 235 
 236   // Counts
 237   static long _total_bytes;
 238   static int  _total_methods;
 239 
 240   static long _total_blocks;
 241   static int  _max_method_blocks;
 242 
 243   static long _total_edges;
 244   static int  _max_block_edges;
 245 
 246   static long _total_exc_edges;
 247   static int  _max_block_exc_edges;
 248 
 249   static long _total_method_locals;
 250   static int  _max_method_locals;
 251   
 252   static long _total_locals_queried;
 253   static long _total_live_locals_queried;
 254   
 255   static long _total_visits;
 256 
 257 #endif
 258 
 259  public:
 260   // Create a liveness analyzer for a method
 261   MethodLiveness(Arena* arena, ciMethod* method);
 262 
 263   // Compute liveness information for the method
 264   void compute_liveness();
 265 
 266   // Find out which locals are live at a specific bci.
 267   MethodLivenessResult get_liveness_at(int bci);
 268 
 269 #ifdef COMPILER1
 270   const BitMap get_bci_block_start() const { return _bci_block_start; }
 271 #endif // COMPILER1
 272 
 273   static void print_times() PRODUCT_RETURN;
 274 };