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