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