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