1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/share/vm/compiler/methodLiveness.hpp Sat Dec 01 00:00:00 2007 +0000 1.3 @@ -0,0 +1,271 @@ 1.4 +/* 1.5 + * Copyright 1998-2006 Sun Microsystems, Inc. All Rights Reserved. 1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1.7 + * 1.8 + * This code is free software; you can redistribute it and/or modify it 1.9 + * under the terms of the GNU General Public License version 2 only, as 1.10 + * published by the Free Software Foundation. 1.11 + * 1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT 1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1.15 + * version 2 for more details (a copy is included in the LICENSE file that 1.16 + * accompanied this code). 1.17 + * 1.18 + * You should have received a copy of the GNU General Public License version 1.19 + * 2 along with this work; if not, write to the Free Software Foundation, 1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1.21 + * 1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or 1.24 + * have any questions. 1.25 + * 1.26 + */ 1.27 + 1.28 +class ciMethod; 1.29 + 1.30 +class MethodLivenessResult : public BitMap { 1.31 + private: 1.32 + bool _is_valid; 1.33 + 1.34 + public: 1.35 + MethodLivenessResult(uintptr_t* map, idx_t size_in_bits) 1.36 + : BitMap(map, size_in_bits) 1.37 + , _is_valid(false) 1.38 + {} 1.39 + 1.40 + MethodLivenessResult(idx_t size_in_bits) 1.41 + : BitMap(size_in_bits) 1.42 + , _is_valid(false) 1.43 + {} 1.44 + 1.45 + void set_is_valid() { _is_valid = true; } 1.46 + bool is_valid() { return _is_valid; } 1.47 +}; 1.48 + 1.49 +class MethodLiveness : public ResourceObj { 1.50 + public: 1.51 + // The BasicBlock class is used to represent a basic block in the 1.52 + // liveness analysis. 1.53 + class BasicBlock : public ResourceObj { 1.54 + private: 1.55 + // This class is only used by the MethodLiveness class. 1.56 + friend class MethodLiveness; 1.57 + 1.58 + // The analyzer which created this basic block. 1.59 + MethodLiveness* _analyzer; 1.60 + 1.61 + // The range of this basic block is [start_bci,limit_bci) 1.62 + int _start_bci; 1.63 + int _limit_bci; 1.64 + 1.65 + // The liveness at the start of the block; 1.66 + BitMap _entry; 1.67 + 1.68 + // The summarized liveness effects of our direct successors reached 1.69 + // by normal control flow 1.70 + BitMap _normal_exit; 1.71 + 1.72 + // The summarized liveness effects of our direct successors reached 1.73 + // by exceptional control flow 1.74 + BitMap _exception_exit; 1.75 + 1.76 + // These members hold the results of the last call to 1.77 + // compute_gen_kill_range(). _gen is the set of locals 1.78 + // used before they are defined in the range. _kill is the 1.79 + // set of locals defined before they are used. 1.80 + BitMap _gen; 1.81 + BitMap _kill; 1.82 + int _last_bci; 1.83 + 1.84 + // A list of all blocks which could come directly before this one 1.85 + // in normal (non-exceptional) control flow. We propagate liveness 1.86 + // information to these blocks. 1.87 + GrowableArray<BasicBlock*>* _normal_predecessors; 1.88 + 1.89 + // A list of all blocks which could come directly before this one 1.90 + // in exceptional control flow. 1.91 + GrowableArray<BasicBlock*>* _exception_predecessors; 1.92 + 1.93 + // The following fields are used to manage a work list used in the 1.94 + // dataflow. 1.95 + BasicBlock *_next; 1.96 + bool _on_work_list; 1.97 + 1.98 + // Our successors call this method to merge liveness information into 1.99 + // our _normal_exit member. 1.100 + bool merge_normal(BitMap other); 1.101 + 1.102 + // Our successors call this method to merge liveness information into 1.103 + // our _exception_exit member. 1.104 + bool merge_exception(BitMap other); 1.105 + 1.106 + // This helper routine is used to help compute the gen/kill pair for 1.107 + // the block. It is also used to answer queries. 1.108 + void compute_gen_kill_range(ciBytecodeStream *bytes); 1.109 + 1.110 + // Compute the gen/kill effect of a single instruction. 1.111 + void compute_gen_kill_single(ciBytecodeStream *instruction); 1.112 + 1.113 + // Helpers for compute_gen_kill_single. 1.114 + void load_one(int local); 1.115 + void load_two(int local); 1.116 + void store_one(int local); 1.117 + void store_two(int local); 1.118 + 1.119 + BasicBlock(MethodLiveness *analyzer, int start, int limit); 1.120 + 1.121 + // -- Accessors 1.122 + 1.123 + int start_bci() const { return _start_bci; } 1.124 + 1.125 + int limit_bci() const { return _limit_bci; } 1.126 + void set_limit_bci(int limit) { _limit_bci = limit; } 1.127 + 1.128 + BasicBlock *next() const { return _next; } 1.129 + void set_next(BasicBlock *next) { _next = next; } 1.130 + 1.131 + bool on_work_list() const { return _on_work_list; } 1.132 + void set_on_work_list(bool val) { _on_work_list = val; } 1.133 + 1.134 + // -- Flow graph construction. 1.135 + 1.136 + // Add a basic block to our list of normal predecessors. 1.137 + void add_normal_predecessor(BasicBlock *pred) { 1.138 + _normal_predecessors->append_if_missing(pred); 1.139 + } 1.140 + 1.141 + // Add a basic block to our list of exceptional predecessors 1.142 + void add_exception_predecessor(BasicBlock *pred) { 1.143 + _exception_predecessors->append_if_missing(pred); 1.144 + } 1.145 + 1.146 + // Split the basic block at splitBci. This basic block 1.147 + // becomes the second half. The first half is newly created. 1.148 + BasicBlock *split(int splitBci); 1.149 + 1.150 + // -- Dataflow. 1.151 + 1.152 + void compute_gen_kill(ciMethod* method); 1.153 + 1.154 + // Propagate changes from this basic block 1.155 + void propagate(MethodLiveness *ml); 1.156 + 1.157 + // -- Query. 1.158 + 1.159 + MethodLivenessResult get_liveness_at(ciMethod* method, int bci); 1.160 + 1.161 + // -- Debugging. 1.162 + 1.163 + void print_on(outputStream *os) const PRODUCT_RETURN; 1.164 + 1.165 + }; // End of MethodLiveness::BasicBlock 1.166 + 1.167 + private: 1.168 + // The method we are analyzing. 1.169 + ciMethod* _method; 1.170 + ciMethod* method() const { return _method; } 1.171 + 1.172 + // The arena for storing structures... 1.173 + Arena* _arena; 1.174 + Arena* arena() const { return _arena; } 1.175 + 1.176 + // We cache the length of the method. 1.177 + int _code_size; 1.178 + 1.179 + // The size of a BitMap. 1.180 + int _bit_map_size_bits; 1.181 + int _bit_map_size_words; 1.182 + 1.183 + // A list of all BasicBlocks. 1.184 + BasicBlock **_block_list; 1.185 + 1.186 + // number of blocks 1.187 + int _block_count; 1.188 + 1.189 + // Keeps track of bci->block mapping. One entry for each bci. Only block starts are 1.190 + // recorded. 1.191 + GrowableArray<BasicBlock*>* _block_map; 1.192 + 1.193 + // Our work list. 1.194 + BasicBlock *_work_list; 1.195 + 1.196 +#ifdef COMPILER1 1.197 + // bcis where blocks start are marked 1.198 + BitMap _bci_block_start; 1.199 +#endif // COMPILER1 1.200 + 1.201 + // -- Graph construction & Analysis 1.202 + 1.203 + // Compute ranges and predecessors for basic blocks. 1.204 + void init_basic_blocks(); 1.205 + 1.206 + // Compute gen/kill information for all basic blocks. 1.207 + void init_gen_kill(); 1.208 + 1.209 + // Perform the dataflow. 1.210 + void propagate_liveness(); 1.211 + 1.212 + // The class MethodLiveness::BasicBlock needs special access to some 1.213 + // of our members. 1.214 + friend class MethodLiveness::BasicBlock; 1.215 + 1.216 + // And accessors. 1.217 + int bit_map_size_bits() const { return _bit_map_size_bits; } 1.218 + int bit_map_size_words() const { return _bit_map_size_words; } 1.219 + 1.220 + // Work list manipulation routines. Called internally by BasicBlock. 1.221 + BasicBlock *work_list_get(); 1.222 + void work_list_add(BasicBlock *block); 1.223 + 1.224 + // -- Timing and Statistics. 1.225 + 1.226 + 1.227 + // Timers 1.228 + static elapsedTimer _time_build_graph; 1.229 + static elapsedTimer _time_gen_kill; 1.230 + static elapsedTimer _time_flow; 1.231 + static elapsedTimer _time_query; 1.232 + static elapsedTimer _time_total; 1.233 + 1.234 +#ifndef PRODUCT 1.235 + 1.236 + // Counts 1.237 + static long _total_bytes; 1.238 + static int _total_methods; 1.239 + 1.240 + static long _total_blocks; 1.241 + static int _max_method_blocks; 1.242 + 1.243 + static long _total_edges; 1.244 + static int _max_block_edges; 1.245 + 1.246 + static long _total_exc_edges; 1.247 + static int _max_block_exc_edges; 1.248 + 1.249 + static long _total_method_locals; 1.250 + static int _max_method_locals; 1.251 + 1.252 + static long _total_locals_queried; 1.253 + static long _total_live_locals_queried; 1.254 + 1.255 + static long _total_visits; 1.256 + 1.257 +#endif 1.258 + 1.259 + public: 1.260 + // Create a liveness analyzer for a method 1.261 + MethodLiveness(Arena* arena, ciMethod* method); 1.262 + 1.263 + // Compute liveness information for the method 1.264 + void compute_liveness(); 1.265 + 1.266 + // Find out which locals are live at a specific bci. 1.267 + MethodLivenessResult get_liveness_at(int bci); 1.268 + 1.269 +#ifdef COMPILER1 1.270 + const BitMap get_bci_block_start() const { return _bci_block_start; } 1.271 +#endif // COMPILER1 1.272 + 1.273 + static void print_times() PRODUCT_RETURN; 1.274 +};