methodLiveness.hpp revision 1472:c18cbe5936b8
1/* 2 * Copyright (c) 1998, 2006, 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 25class ciMethod; 26 27class MethodLivenessResult : public BitMap { 28 private: 29 bool _is_valid; 30 31 public: 32 MethodLivenessResult(BitMap::bm_word_t* map, idx_t size_in_bits) 33 : BitMap(map, size_in_bits) 34 , _is_valid(false) 35 {} 36 37 MethodLivenessResult(idx_t size_in_bits) 38 : BitMap(size_in_bits) 39 , _is_valid(false) 40 {} 41 42 void set_is_valid() { _is_valid = true; } 43 bool is_valid() { return _is_valid; } 44}; 45 46class MethodLiveness : public ResourceObj { 47 public: 48 // The BasicBlock class is used to represent a basic block in the 49 // liveness analysis. 50 class BasicBlock : public ResourceObj { 51 private: 52 // This class is only used by the MethodLiveness class. 53 friend class MethodLiveness; 54 55 // The analyzer which created this basic block. 56 MethodLiveness* _analyzer; 57 58 // The range of this basic block is [start_bci,limit_bci) 59 int _start_bci; 60 int _limit_bci; 61 62 // The liveness at the start of the block; 63 BitMap _entry; 64 65 // The summarized liveness effects of our direct successors reached 66 // by normal control flow 67 BitMap _normal_exit; 68 69 // The summarized liveness effects of our direct successors reached 70 // by exceptional control flow 71 BitMap _exception_exit; 72 73 // These members hold the results of the last call to 74 // compute_gen_kill_range(). _gen is the set of locals 75 // used before they are defined in the range. _kill is the 76 // set of locals defined before they are used. 77 BitMap _gen; 78 BitMap _kill; 79 int _last_bci; 80 81 // A list of all blocks which could come directly before this one 82 // in normal (non-exceptional) control flow. We propagate liveness 83 // information to these blocks. 84 GrowableArray<BasicBlock*>* _normal_predecessors; 85 86 // A list of all blocks which could come directly before this one 87 // in exceptional control flow. 88 GrowableArray<BasicBlock*>* _exception_predecessors; 89 90 // The following fields are used to manage a work list used in the 91 // dataflow. 92 BasicBlock *_next; 93 bool _on_work_list; 94 95 // Our successors call this method to merge liveness information into 96 // our _normal_exit member. 97 bool merge_normal(BitMap other); 98 99 // Our successors call this method to merge liveness information into 100 // our _exception_exit member. 101 bool merge_exception(BitMap other); 102 103 // This helper routine is used to help compute the gen/kill pair for 104 // the block. It is also used to answer queries. 105 void compute_gen_kill_range(ciBytecodeStream *bytes); 106 107 // Compute the gen/kill effect of a single instruction. 108 void compute_gen_kill_single(ciBytecodeStream *instruction); 109 110 // Helpers for compute_gen_kill_single. 111 void load_one(int local); 112 void load_two(int local); 113 void store_one(int local); 114 void store_two(int local); 115 116 BasicBlock(MethodLiveness *analyzer, int start, int limit); 117 118 // -- Accessors 119 120 int start_bci() const { return _start_bci; } 121 122 int limit_bci() const { return _limit_bci; } 123 void set_limit_bci(int limit) { _limit_bci = limit; } 124 125 BasicBlock *next() const { return _next; } 126 void set_next(BasicBlock *next) { _next = next; } 127 128 bool on_work_list() const { return _on_work_list; } 129 void set_on_work_list(bool val) { _on_work_list = val; } 130 131 // -- Flow graph construction. 132 133 // Add a basic block to our list of normal predecessors. 134 void add_normal_predecessor(BasicBlock *pred) { 135 _normal_predecessors->append_if_missing(pred); 136 } 137 138 // Add a basic block to our list of exceptional predecessors 139 void add_exception_predecessor(BasicBlock *pred) { 140 _exception_predecessors->append_if_missing(pred); 141 } 142 143 // Split the basic block at splitBci. This basic block 144 // becomes the second half. The first half is newly created. 145 BasicBlock *split(int splitBci); 146 147 // -- Dataflow. 148 149 void compute_gen_kill(ciMethod* method); 150 151 // Propagate changes from this basic block 152 void propagate(MethodLiveness *ml); 153 154 // -- Query. 155 156 MethodLivenessResult get_liveness_at(ciMethod* method, int bci); 157 158 // -- Debugging. 159 160 void print_on(outputStream *os) const PRODUCT_RETURN; 161 162 }; // End of MethodLiveness::BasicBlock 163 164 private: 165 // The method we are analyzing. 166 ciMethod* _method; 167 ciMethod* method() const { return _method; } 168 169 // The arena for storing structures... 170 Arena* _arena; 171 Arena* arena() const { return _arena; } 172 173 // We cache the length of the method. 174 int _code_size; 175 176 // The size of a BitMap. 177 int _bit_map_size_bits; 178 int _bit_map_size_words; 179 180 // A list of all BasicBlocks. 181 BasicBlock **_block_list; 182 183 // number of blocks 184 int _block_count; 185 186 // Keeps track of bci->block mapping. One entry for each bci. Only block starts are 187 // recorded. 188 GrowableArray<BasicBlock*>* _block_map; 189 190 // Our work list. 191 BasicBlock *_work_list; 192 193#ifdef COMPILER1 194 // bcis where blocks start are marked 195 BitMap _bci_block_start; 196#endif // COMPILER1 197 198 // -- Graph construction & Analysis 199 200 // Compute ranges and predecessors for basic blocks. 201 void init_basic_blocks(); 202 203 // Compute gen/kill information for all basic blocks. 204 void init_gen_kill(); 205 206 // Perform the dataflow. 207 void propagate_liveness(); 208 209 // The class MethodLiveness::BasicBlock needs special access to some 210 // of our members. 211 friend class MethodLiveness::BasicBlock; 212 213 // And accessors. 214 int bit_map_size_bits() const { return _bit_map_size_bits; } 215 int bit_map_size_words() const { return _bit_map_size_words; } 216 217 // Work list manipulation routines. Called internally by BasicBlock. 218 BasicBlock *work_list_get(); 219 void work_list_add(BasicBlock *block); 220 221 // -- Timing and Statistics. 222 223 224 // Timers 225 static elapsedTimer _time_build_graph; 226 static elapsedTimer _time_gen_kill; 227 static elapsedTimer _time_flow; 228 static elapsedTimer _time_query; 229 static elapsedTimer _time_total; 230 231#ifndef PRODUCT 232 233 // Counts 234 static long _total_bytes; 235 static int _total_methods; 236 237 static long _total_blocks; 238 static int _max_method_blocks; 239 240 static long _total_edges; 241 static int _max_block_edges; 242 243 static long _total_exc_edges; 244 static int _max_block_exc_edges; 245 246 static long _total_method_locals; 247 static int _max_method_locals; 248 249 static long _total_locals_queried; 250 static long _total_live_locals_queried; 251 252 static long _total_visits; 253 254#endif 255 256 public: 257 // Create a liveness analyzer for a method 258 MethodLiveness(Arena* arena, ciMethod* method); 259 260 // Compute liveness information for the method 261 void compute_liveness(); 262 263 // Find out which locals are live at a specific bci. 264 MethodLivenessResult get_liveness_at(int bci); 265 266#ifdef COMPILER1 267 const BitMap get_bci_block_start() const { return _bci_block_start; } 268#endif // COMPILER1 269 270 static void print_times() PRODUCT_RETURN; 271}; 272