Tue, 08 Aug 2017 15:57:29 +0800
merge
aoqi@0 | 1 | /* |
aoqi@0 | 2 | * Copyright (c) 1998, 2014, Oracle and/or its affiliates. All rights reserved. |
aoqi@0 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
aoqi@0 | 4 | * |
aoqi@0 | 5 | * This code is free software; you can redistribute it and/or modify it |
aoqi@0 | 6 | * under the terms of the GNU General Public License version 2 only, as |
aoqi@0 | 7 | * published by the Free Software Foundation. |
aoqi@0 | 8 | * |
aoqi@0 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
aoqi@0 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
aoqi@0 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
aoqi@0 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
aoqi@0 | 13 | * accompanied this code). |
aoqi@0 | 14 | * |
aoqi@0 | 15 | * You should have received a copy of the GNU General Public License version |
aoqi@0 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
aoqi@0 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
aoqi@0 | 18 | * |
aoqi@0 | 19 | * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
aoqi@0 | 20 | * or visit www.oracle.com if you need additional information or have any |
aoqi@0 | 21 | * questions. |
aoqi@0 | 22 | * |
aoqi@0 | 23 | */ |
aoqi@0 | 24 | |
aoqi@0 | 25 | #include "precompiled.hpp" |
aoqi@0 | 26 | #include "ci/ciMethod.hpp" |
aoqi@0 | 27 | #include "ci/ciMethodBlocks.hpp" |
aoqi@0 | 28 | #include "ci/ciStreams.hpp" |
aoqi@0 | 29 | #include "compiler/methodLiveness.hpp" |
aoqi@0 | 30 | #include "interpreter/bytecode.hpp" |
aoqi@0 | 31 | #include "interpreter/bytecodes.hpp" |
aoqi@0 | 32 | #include "memory/allocation.inline.hpp" |
aoqi@0 | 33 | #include "utilities/bitMap.inline.hpp" |
aoqi@0 | 34 | |
aoqi@0 | 35 | PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC |
aoqi@0 | 36 | |
aoqi@0 | 37 | // The MethodLiveness class performs a simple liveness analysis on a method |
aoqi@0 | 38 | // in order to decide which locals are live (that is, will be used again) at |
aoqi@0 | 39 | // a particular bytecode index (bci). |
aoqi@0 | 40 | // |
aoqi@0 | 41 | // The algorithm goes: |
aoqi@0 | 42 | // |
aoqi@0 | 43 | // 1. Break the method into a set of basic blocks. For each basic block we |
aoqi@0 | 44 | // also keep track of its set of predecessors through normal control flow |
aoqi@0 | 45 | // and predecessors through exceptional control flow. |
aoqi@0 | 46 | // |
aoqi@0 | 47 | // 2. For each basic block, compute two sets, gen (the set of values used before |
aoqi@0 | 48 | // they are defined) and kill (the set of values defined before they are used) |
aoqi@0 | 49 | // in the basic block. A basic block "needs" the locals in its gen set to |
aoqi@0 | 50 | // perform its computation. A basic block "provides" values for the locals in |
aoqi@0 | 51 | // its kill set, allowing a need from a successor to be ignored. |
aoqi@0 | 52 | // |
aoqi@0 | 53 | // 3. Liveness information (the set of locals which are needed) is pushed backwards through |
aoqi@0 | 54 | // the program, from blocks to their predecessors. We compute and store liveness |
aoqi@0 | 55 | // information for the normal/exceptional exit paths for each basic block. When |
aoqi@0 | 56 | // this process reaches a fixed point, we are done. |
aoqi@0 | 57 | // |
aoqi@0 | 58 | // 4. When we are asked about the liveness at a particular bci with a basic block, we |
aoqi@0 | 59 | // compute gen/kill sets which represent execution from that bci to the exit of |
aoqi@0 | 60 | // its blocks. We then compose this range gen/kill information with the normal |
aoqi@0 | 61 | // and exceptional exit information for the block to produce liveness information |
aoqi@0 | 62 | // at that bci. |
aoqi@0 | 63 | // |
aoqi@0 | 64 | // The algorithm is approximate in many respects. Notably: |
aoqi@0 | 65 | // |
aoqi@0 | 66 | // 1. We do not do the analysis necessary to match jsr's with the appropriate ret. |
aoqi@0 | 67 | // Instead we make the conservative assumption that any ret can return to any |
aoqi@0 | 68 | // jsr return site. |
aoqi@0 | 69 | // 2. Instead of computing the effects of exceptions at every instruction, we |
aoqi@0 | 70 | // summarize the effects of all exceptional continuations from the block as |
aoqi@0 | 71 | // a single set (_exception_exit), losing some information but simplifying the |
aoqi@0 | 72 | // analysis. |
aoqi@0 | 73 | |
aoqi@0 | 74 | |
aoqi@0 | 75 | //-------------------------------------------------------------------------- |
aoqi@0 | 76 | // The BitCounter class is used for counting the number of bits set in |
aoqi@0 | 77 | // some BitMap. It is only used when collecting liveness statistics. |
aoqi@0 | 78 | |
aoqi@0 | 79 | #ifndef PRODUCT |
aoqi@0 | 80 | |
aoqi@0 | 81 | class BitCounter: public BitMapClosure { |
aoqi@0 | 82 | private: |
aoqi@0 | 83 | int _count; |
aoqi@0 | 84 | public: |
aoqi@0 | 85 | BitCounter() : _count(0) {} |
aoqi@0 | 86 | |
aoqi@0 | 87 | // Callback when bit in map is set |
aoqi@0 | 88 | virtual bool do_bit(size_t offset) { |
aoqi@0 | 89 | _count++; |
aoqi@0 | 90 | return true; |
aoqi@0 | 91 | } |
aoqi@0 | 92 | |
aoqi@0 | 93 | int count() { |
aoqi@0 | 94 | return _count; |
aoqi@0 | 95 | } |
aoqi@0 | 96 | }; |
aoqi@0 | 97 | |
aoqi@0 | 98 | |
aoqi@0 | 99 | //-------------------------------------------------------------------------- |
aoqi@0 | 100 | |
aoqi@0 | 101 | |
aoqi@0 | 102 | // Counts |
aoqi@0 | 103 | long MethodLiveness::_total_bytes = 0; |
aoqi@0 | 104 | int MethodLiveness::_total_methods = 0; |
aoqi@0 | 105 | |
aoqi@0 | 106 | long MethodLiveness::_total_blocks = 0; |
aoqi@0 | 107 | int MethodLiveness::_max_method_blocks = 0; |
aoqi@0 | 108 | |
aoqi@0 | 109 | long MethodLiveness::_total_edges = 0; |
aoqi@0 | 110 | int MethodLiveness::_max_block_edges = 0; |
aoqi@0 | 111 | |
aoqi@0 | 112 | long MethodLiveness::_total_exc_edges = 0; |
aoqi@0 | 113 | int MethodLiveness::_max_block_exc_edges = 0; |
aoqi@0 | 114 | |
aoqi@0 | 115 | long MethodLiveness::_total_method_locals = 0; |
aoqi@0 | 116 | int MethodLiveness::_max_method_locals = 0; |
aoqi@0 | 117 | |
aoqi@0 | 118 | long MethodLiveness::_total_locals_queried = 0; |
aoqi@0 | 119 | long MethodLiveness::_total_live_locals_queried = 0; |
aoqi@0 | 120 | |
aoqi@0 | 121 | long MethodLiveness::_total_visits = 0; |
aoqi@0 | 122 | |
aoqi@0 | 123 | #endif |
aoqi@0 | 124 | |
aoqi@0 | 125 | // Timers |
aoqi@0 | 126 | elapsedTimer MethodLiveness::_time_build_graph; |
aoqi@0 | 127 | elapsedTimer MethodLiveness::_time_gen_kill; |
aoqi@0 | 128 | elapsedTimer MethodLiveness::_time_flow; |
aoqi@0 | 129 | elapsedTimer MethodLiveness::_time_query; |
aoqi@0 | 130 | elapsedTimer MethodLiveness::_time_total; |
aoqi@0 | 131 | |
aoqi@0 | 132 | MethodLiveness::MethodLiveness(Arena* arena, ciMethod* method) |
aoqi@0 | 133 | #ifdef COMPILER1 |
aoqi@0 | 134 | : _bci_block_start((uintptr_t*)arena->Amalloc((method->code_size() >> LogBitsPerByte) + 1), method->code_size()) |
aoqi@0 | 135 | #endif |
aoqi@0 | 136 | { |
aoqi@0 | 137 | _arena = arena; |
aoqi@0 | 138 | _method = method; |
aoqi@0 | 139 | _bit_map_size_bits = method->max_locals(); |
aoqi@0 | 140 | _bit_map_size_words = (_bit_map_size_bits / sizeof(unsigned int)) + 1; |
aoqi@0 | 141 | |
aoqi@0 | 142 | #ifdef COMPILER1 |
aoqi@0 | 143 | _bci_block_start.clear(); |
aoqi@0 | 144 | #endif |
aoqi@0 | 145 | } |
aoqi@0 | 146 | |
aoqi@0 | 147 | void MethodLiveness::compute_liveness() { |
aoqi@0 | 148 | #ifndef PRODUCT |
aoqi@0 | 149 | if (TraceLivenessGen) { |
aoqi@0 | 150 | tty->print_cr("################################################################"); |
aoqi@0 | 151 | tty->print("# Computing liveness information for "); |
aoqi@0 | 152 | method()->print_short_name(); |
aoqi@0 | 153 | } |
aoqi@0 | 154 | |
aoqi@0 | 155 | if (TimeLivenessAnalysis) _time_total.start(); |
aoqi@0 | 156 | #endif |
aoqi@0 | 157 | |
aoqi@0 | 158 | { |
aoqi@0 | 159 | TraceTime buildGraph(NULL, &_time_build_graph, TimeLivenessAnalysis); |
aoqi@0 | 160 | init_basic_blocks(); |
aoqi@0 | 161 | } |
aoqi@0 | 162 | { |
aoqi@0 | 163 | TraceTime genKill(NULL, &_time_gen_kill, TimeLivenessAnalysis); |
aoqi@0 | 164 | init_gen_kill(); |
aoqi@0 | 165 | } |
aoqi@0 | 166 | { |
aoqi@0 | 167 | TraceTime flow(NULL, &_time_flow, TimeLivenessAnalysis); |
aoqi@0 | 168 | propagate_liveness(); |
aoqi@0 | 169 | } |
aoqi@0 | 170 | |
aoqi@0 | 171 | #ifndef PRODUCT |
aoqi@0 | 172 | if (TimeLivenessAnalysis) _time_total.stop(); |
aoqi@0 | 173 | |
aoqi@0 | 174 | if (TimeLivenessAnalysis) { |
aoqi@0 | 175 | // Collect statistics |
aoqi@0 | 176 | _total_bytes += method()->code_size(); |
aoqi@0 | 177 | _total_methods++; |
aoqi@0 | 178 | |
aoqi@0 | 179 | int num_blocks = _block_count; |
aoqi@0 | 180 | _total_blocks += num_blocks; |
aoqi@0 | 181 | _max_method_blocks = MAX2(num_blocks,_max_method_blocks); |
aoqi@0 | 182 | |
aoqi@0 | 183 | for (int i=0; i<num_blocks; i++) { |
aoqi@0 | 184 | BasicBlock *block = _block_list[i]; |
aoqi@0 | 185 | |
aoqi@0 | 186 | int numEdges = block->_normal_predecessors->length(); |
aoqi@0 | 187 | int numExcEdges = block->_exception_predecessors->length(); |
aoqi@0 | 188 | |
aoqi@0 | 189 | _total_edges += numEdges; |
aoqi@0 | 190 | _total_exc_edges += numExcEdges; |
aoqi@0 | 191 | _max_block_edges = MAX2(numEdges,_max_block_edges); |
aoqi@0 | 192 | _max_block_exc_edges = MAX2(numExcEdges,_max_block_exc_edges); |
aoqi@0 | 193 | } |
aoqi@0 | 194 | |
aoqi@0 | 195 | int numLocals = _bit_map_size_bits; |
aoqi@0 | 196 | _total_method_locals += numLocals; |
aoqi@0 | 197 | _max_method_locals = MAX2(numLocals,_max_method_locals); |
aoqi@0 | 198 | } |
aoqi@0 | 199 | #endif |
aoqi@0 | 200 | } |
aoqi@0 | 201 | |
aoqi@0 | 202 | |
aoqi@0 | 203 | void MethodLiveness::init_basic_blocks() { |
aoqi@0 | 204 | bool bailout = false; |
aoqi@0 | 205 | |
aoqi@0 | 206 | int method_len = method()->code_size(); |
aoqi@0 | 207 | ciMethodBlocks *mblocks = method()->get_method_blocks(); |
aoqi@0 | 208 | |
aoqi@0 | 209 | // Create an array to store the bci->BasicBlock mapping. |
aoqi@0 | 210 | _block_map = new (arena()) GrowableArray<BasicBlock*>(arena(), method_len, method_len, NULL); |
aoqi@0 | 211 | |
aoqi@0 | 212 | _block_count = mblocks->num_blocks(); |
aoqi@0 | 213 | _block_list = (BasicBlock **) arena()->Amalloc(sizeof(BasicBlock *) * _block_count); |
aoqi@0 | 214 | |
aoqi@0 | 215 | // Used for patching up jsr/ret control flow. |
aoqi@0 | 216 | GrowableArray<BasicBlock*>* jsr_exit_list = new GrowableArray<BasicBlock*>(5); |
aoqi@0 | 217 | GrowableArray<BasicBlock*>* ret_list = new GrowableArray<BasicBlock*>(5); |
aoqi@0 | 218 | |
aoqi@0 | 219 | // generate our block list from ciMethodBlocks |
aoqi@0 | 220 | for (int blk = 0; blk < _block_count; blk++) { |
aoqi@0 | 221 | ciBlock *cib = mblocks->block(blk); |
aoqi@0 | 222 | int start_bci = cib->start_bci(); |
aoqi@0 | 223 | _block_list[blk] = new (arena()) BasicBlock(this, start_bci, cib->limit_bci()); |
aoqi@0 | 224 | _block_map->at_put(start_bci, _block_list[blk]); |
aoqi@0 | 225 | #ifdef COMPILER1 |
aoqi@0 | 226 | // mark all bcis where a new basic block starts |
aoqi@0 | 227 | _bci_block_start.set_bit(start_bci); |
aoqi@0 | 228 | #endif // COMPILER1 |
aoqi@0 | 229 | } |
aoqi@0 | 230 | // fill in the predecessors of blocks |
aoqi@0 | 231 | ciBytecodeStream bytes(method()); |
aoqi@0 | 232 | |
aoqi@0 | 233 | for (int blk = 0; blk < _block_count; blk++) { |
aoqi@0 | 234 | BasicBlock *current_block = _block_list[blk]; |
aoqi@0 | 235 | int bci = mblocks->block(blk)->control_bci(); |
aoqi@0 | 236 | |
aoqi@0 | 237 | if (bci == ciBlock::fall_through_bci) { |
aoqi@0 | 238 | int limit = current_block->limit_bci(); |
aoqi@0 | 239 | if (limit < method_len) { |
aoqi@0 | 240 | BasicBlock *next = _block_map->at(limit); |
aoqi@0 | 241 | assert( next != NULL, "must be a block immediately following this one."); |
aoqi@0 | 242 | next->add_normal_predecessor(current_block); |
aoqi@0 | 243 | } |
aoqi@0 | 244 | continue; |
aoqi@0 | 245 | } |
aoqi@0 | 246 | bytes.reset_to_bci(bci); |
aoqi@0 | 247 | Bytecodes::Code code = bytes.next(); |
aoqi@0 | 248 | BasicBlock *dest; |
aoqi@0 | 249 | |
aoqi@0 | 250 | // Now we need to interpret the instruction's effect |
aoqi@0 | 251 | // on control flow. |
aoqi@0 | 252 | assert (current_block != NULL, "we must have a current block"); |
aoqi@0 | 253 | switch (code) { |
aoqi@0 | 254 | case Bytecodes::_ifeq: |
aoqi@0 | 255 | case Bytecodes::_ifne: |
aoqi@0 | 256 | case Bytecodes::_iflt: |
aoqi@0 | 257 | case Bytecodes::_ifge: |
aoqi@0 | 258 | case Bytecodes::_ifgt: |
aoqi@0 | 259 | case Bytecodes::_ifle: |
aoqi@0 | 260 | case Bytecodes::_if_icmpeq: |
aoqi@0 | 261 | case Bytecodes::_if_icmpne: |
aoqi@0 | 262 | case Bytecodes::_if_icmplt: |
aoqi@0 | 263 | case Bytecodes::_if_icmpge: |
aoqi@0 | 264 | case Bytecodes::_if_icmpgt: |
aoqi@0 | 265 | case Bytecodes::_if_icmple: |
aoqi@0 | 266 | case Bytecodes::_if_acmpeq: |
aoqi@0 | 267 | case Bytecodes::_if_acmpne: |
aoqi@0 | 268 | case Bytecodes::_ifnull: |
aoqi@0 | 269 | case Bytecodes::_ifnonnull: |
aoqi@0 | 270 | // Two way branch. Set predecessors at each destination. |
aoqi@0 | 271 | dest = _block_map->at(bytes.next_bci()); |
aoqi@0 | 272 | assert(dest != NULL, "must be a block immediately following this one."); |
aoqi@0 | 273 | dest->add_normal_predecessor(current_block); |
aoqi@0 | 274 | |
aoqi@0 | 275 | dest = _block_map->at(bytes.get_dest()); |
aoqi@0 | 276 | assert(dest != NULL, "branch desination must start a block."); |
aoqi@0 | 277 | dest->add_normal_predecessor(current_block); |
aoqi@0 | 278 | break; |
aoqi@0 | 279 | case Bytecodes::_goto: |
aoqi@0 | 280 | dest = _block_map->at(bytes.get_dest()); |
aoqi@0 | 281 | assert(dest != NULL, "branch desination must start a block."); |
aoqi@0 | 282 | dest->add_normal_predecessor(current_block); |
aoqi@0 | 283 | break; |
aoqi@0 | 284 | case Bytecodes::_goto_w: |
aoqi@0 | 285 | dest = _block_map->at(bytes.get_far_dest()); |
aoqi@0 | 286 | assert(dest != NULL, "branch desination must start a block."); |
aoqi@0 | 287 | dest->add_normal_predecessor(current_block); |
aoqi@0 | 288 | break; |
aoqi@0 | 289 | case Bytecodes::_tableswitch: |
aoqi@0 | 290 | { |
aoqi@0 | 291 | Bytecode_tableswitch tableswitch(&bytes); |
aoqi@0 | 292 | |
aoqi@0 | 293 | int len = tableswitch.length(); |
aoqi@0 | 294 | |
aoqi@0 | 295 | dest = _block_map->at(bci + tableswitch.default_offset()); |
aoqi@0 | 296 | assert(dest != NULL, "branch desination must start a block."); |
aoqi@0 | 297 | dest->add_normal_predecessor(current_block); |
aoqi@0 | 298 | while (--len >= 0) { |
aoqi@0 | 299 | dest = _block_map->at(bci + tableswitch.dest_offset_at(len)); |
aoqi@0 | 300 | assert(dest != NULL, "branch desination must start a block."); |
aoqi@0 | 301 | dest->add_normal_predecessor(current_block); |
aoqi@0 | 302 | } |
aoqi@0 | 303 | break; |
aoqi@0 | 304 | } |
aoqi@0 | 305 | |
aoqi@0 | 306 | case Bytecodes::_lookupswitch: |
aoqi@0 | 307 | { |
aoqi@0 | 308 | Bytecode_lookupswitch lookupswitch(&bytes); |
aoqi@0 | 309 | |
aoqi@0 | 310 | int npairs = lookupswitch.number_of_pairs(); |
aoqi@0 | 311 | |
aoqi@0 | 312 | dest = _block_map->at(bci + lookupswitch.default_offset()); |
aoqi@0 | 313 | assert(dest != NULL, "branch desination must start a block."); |
aoqi@0 | 314 | dest->add_normal_predecessor(current_block); |
aoqi@0 | 315 | while(--npairs >= 0) { |
aoqi@0 | 316 | LookupswitchPair pair = lookupswitch.pair_at(npairs); |
aoqi@0 | 317 | dest = _block_map->at( bci + pair.offset()); |
aoqi@0 | 318 | assert(dest != NULL, "branch desination must start a block."); |
aoqi@0 | 319 | dest->add_normal_predecessor(current_block); |
aoqi@0 | 320 | } |
aoqi@0 | 321 | break; |
aoqi@0 | 322 | } |
aoqi@0 | 323 | |
aoqi@0 | 324 | case Bytecodes::_jsr: |
aoqi@0 | 325 | { |
aoqi@0 | 326 | assert(bytes.is_wide()==false, "sanity check"); |
aoqi@0 | 327 | dest = _block_map->at(bytes.get_dest()); |
aoqi@0 | 328 | assert(dest != NULL, "branch desination must start a block."); |
aoqi@0 | 329 | dest->add_normal_predecessor(current_block); |
aoqi@0 | 330 | BasicBlock *jsrExit = _block_map->at(current_block->limit_bci()); |
aoqi@0 | 331 | assert(jsrExit != NULL, "jsr return bci must start a block."); |
aoqi@0 | 332 | jsr_exit_list->append(jsrExit); |
aoqi@0 | 333 | break; |
aoqi@0 | 334 | } |
aoqi@0 | 335 | case Bytecodes::_jsr_w: |
aoqi@0 | 336 | { |
aoqi@0 | 337 | dest = _block_map->at(bytes.get_far_dest()); |
aoqi@0 | 338 | assert(dest != NULL, "branch desination must start a block."); |
aoqi@0 | 339 | dest->add_normal_predecessor(current_block); |
aoqi@0 | 340 | BasicBlock *jsrExit = _block_map->at(current_block->limit_bci()); |
aoqi@0 | 341 | assert(jsrExit != NULL, "jsr return bci must start a block."); |
aoqi@0 | 342 | jsr_exit_list->append(jsrExit); |
aoqi@0 | 343 | break; |
aoqi@0 | 344 | } |
aoqi@0 | 345 | |
aoqi@0 | 346 | case Bytecodes::_wide: |
aoqi@0 | 347 | assert(false, "wide opcodes should not be seen here"); |
aoqi@0 | 348 | break; |
aoqi@0 | 349 | case Bytecodes::_athrow: |
aoqi@0 | 350 | case Bytecodes::_ireturn: |
aoqi@0 | 351 | case Bytecodes::_lreturn: |
aoqi@0 | 352 | case Bytecodes::_freturn: |
aoqi@0 | 353 | case Bytecodes::_dreturn: |
aoqi@0 | 354 | case Bytecodes::_areturn: |
aoqi@0 | 355 | case Bytecodes::_return: |
aoqi@0 | 356 | // These opcodes are not the normal predecessors of any other opcodes. |
aoqi@0 | 357 | break; |
aoqi@0 | 358 | case Bytecodes::_ret: |
aoqi@0 | 359 | // We will patch up jsr/rets in a subsequent pass. |
aoqi@0 | 360 | ret_list->append(current_block); |
aoqi@0 | 361 | break; |
aoqi@0 | 362 | case Bytecodes::_breakpoint: |
aoqi@0 | 363 | // Bail out of there are breakpoints in here. |
aoqi@0 | 364 | bailout = true; |
aoqi@0 | 365 | break; |
aoqi@0 | 366 | default: |
aoqi@0 | 367 | // Do nothing. |
aoqi@0 | 368 | break; |
aoqi@0 | 369 | } |
aoqi@0 | 370 | } |
aoqi@0 | 371 | // Patch up the jsr/ret's. We conservatively assume that any ret |
aoqi@0 | 372 | // can return to any jsr site. |
aoqi@0 | 373 | int ret_list_len = ret_list->length(); |
aoqi@0 | 374 | int jsr_exit_list_len = jsr_exit_list->length(); |
aoqi@0 | 375 | if (ret_list_len > 0 && jsr_exit_list_len > 0) { |
aoqi@0 | 376 | for (int i = jsr_exit_list_len - 1; i >= 0; i--) { |
aoqi@0 | 377 | BasicBlock *jsrExit = jsr_exit_list->at(i); |
aoqi@0 | 378 | for (int i = ret_list_len - 1; i >= 0; i--) { |
aoqi@0 | 379 | jsrExit->add_normal_predecessor(ret_list->at(i)); |
aoqi@0 | 380 | } |
aoqi@0 | 381 | } |
aoqi@0 | 382 | } |
aoqi@0 | 383 | |
aoqi@0 | 384 | // Compute exception edges. |
aoqi@0 | 385 | for (int b=_block_count-1; b >= 0; b--) { |
aoqi@0 | 386 | BasicBlock *block = _block_list[b]; |
aoqi@0 | 387 | int block_start = block->start_bci(); |
aoqi@0 | 388 | int block_limit = block->limit_bci(); |
aoqi@0 | 389 | ciExceptionHandlerStream handlers(method()); |
aoqi@0 | 390 | for (; !handlers.is_done(); handlers.next()) { |
aoqi@0 | 391 | ciExceptionHandler* handler = handlers.handler(); |
aoqi@0 | 392 | int start = handler->start(); |
aoqi@0 | 393 | int limit = handler->limit(); |
aoqi@0 | 394 | int handler_bci = handler->handler_bci(); |
aoqi@0 | 395 | |
aoqi@0 | 396 | int intersect_start = MAX2(block_start, start); |
aoqi@0 | 397 | int intersect_limit = MIN2(block_limit, limit); |
aoqi@0 | 398 | if (intersect_start < intersect_limit) { |
aoqi@0 | 399 | // The catch range has a nonempty intersection with this |
aoqi@0 | 400 | // basic block. That means this basic block can be an |
aoqi@0 | 401 | // exceptional predecessor. |
aoqi@0 | 402 | _block_map->at(handler_bci)->add_exception_predecessor(block); |
aoqi@0 | 403 | |
aoqi@0 | 404 | if (handler->is_catch_all()) { |
aoqi@0 | 405 | // This is a catch-all block. |
aoqi@0 | 406 | if (intersect_start == block_start && intersect_limit == block_limit) { |
aoqi@0 | 407 | // The basic block is entirely contained in this catch-all block. |
aoqi@0 | 408 | // Skip the rest of the exception handlers -- they can never be |
aoqi@0 | 409 | // reached in execution. |
aoqi@0 | 410 | break; |
aoqi@0 | 411 | } |
aoqi@0 | 412 | } |
aoqi@0 | 413 | } |
aoqi@0 | 414 | } |
aoqi@0 | 415 | } |
aoqi@0 | 416 | } |
aoqi@0 | 417 | |
aoqi@0 | 418 | void MethodLiveness::init_gen_kill() { |
aoqi@0 | 419 | for (int i=_block_count-1; i >= 0; i--) { |
aoqi@0 | 420 | _block_list[i]->compute_gen_kill(method()); |
aoqi@0 | 421 | } |
aoqi@0 | 422 | } |
aoqi@0 | 423 | |
aoqi@0 | 424 | void MethodLiveness::propagate_liveness() { |
aoqi@0 | 425 | int num_blocks = _block_count; |
aoqi@0 | 426 | BasicBlock *block; |
aoqi@0 | 427 | |
aoqi@0 | 428 | // We start our work list off with all blocks in it. |
aoqi@0 | 429 | // Alternately, we could start off the work list with the list of all |
aoqi@0 | 430 | // blocks which could exit the method directly, along with one block |
aoqi@0 | 431 | // from any infinite loop. If this matters, it can be changed. It |
aoqi@0 | 432 | // may not be clear from looking at the code, but the order of the |
aoqi@0 | 433 | // workList will be the opposite of the creation order of the basic |
aoqi@0 | 434 | // blocks, which should be decent for quick convergence (with the |
aoqi@0 | 435 | // possible exception of exception handlers, which are all created |
aoqi@0 | 436 | // early). |
aoqi@0 | 437 | _work_list = NULL; |
aoqi@0 | 438 | for (int i = 0; i < num_blocks; i++) { |
aoqi@0 | 439 | block = _block_list[i]; |
aoqi@0 | 440 | block->set_next(_work_list); |
aoqi@0 | 441 | block->set_on_work_list(true); |
aoqi@0 | 442 | _work_list = block; |
aoqi@0 | 443 | } |
aoqi@0 | 444 | |
aoqi@0 | 445 | |
aoqi@0 | 446 | while ((block = work_list_get()) != NULL) { |
aoqi@0 | 447 | block->propagate(this); |
aoqi@0 | 448 | NOT_PRODUCT(_total_visits++;) |
aoqi@0 | 449 | } |
aoqi@0 | 450 | } |
aoqi@0 | 451 | |
aoqi@0 | 452 | void MethodLiveness::work_list_add(BasicBlock *block) { |
aoqi@0 | 453 | if (!block->on_work_list()) { |
aoqi@0 | 454 | block->set_next(_work_list); |
aoqi@0 | 455 | block->set_on_work_list(true); |
aoqi@0 | 456 | _work_list = block; |
aoqi@0 | 457 | } |
aoqi@0 | 458 | } |
aoqi@0 | 459 | |
aoqi@0 | 460 | MethodLiveness::BasicBlock *MethodLiveness::work_list_get() { |
aoqi@0 | 461 | BasicBlock *block = _work_list; |
aoqi@0 | 462 | if (block != NULL) { |
aoqi@0 | 463 | block->set_on_work_list(false); |
aoqi@0 | 464 | _work_list = block->next(); |
aoqi@0 | 465 | } |
aoqi@0 | 466 | return block; |
aoqi@0 | 467 | } |
aoqi@0 | 468 | |
aoqi@0 | 469 | |
aoqi@0 | 470 | MethodLivenessResult MethodLiveness::get_liveness_at(int entry_bci) { |
aoqi@0 | 471 | int bci = entry_bci; |
aoqi@0 | 472 | bool is_entry = false; |
aoqi@0 | 473 | if (entry_bci == InvocationEntryBci) { |
aoqi@0 | 474 | is_entry = true; |
aoqi@0 | 475 | bci = 0; |
aoqi@0 | 476 | } |
aoqi@0 | 477 | |
aoqi@0 | 478 | MethodLivenessResult answer((uintptr_t*)NULL,0); |
aoqi@0 | 479 | |
aoqi@0 | 480 | if (_block_count > 0) { |
aoqi@0 | 481 | if (TimeLivenessAnalysis) _time_total.start(); |
aoqi@0 | 482 | if (TimeLivenessAnalysis) _time_query.start(); |
aoqi@0 | 483 | |
aoqi@0 | 484 | assert( 0 <= bci && bci < method()->code_size(), "bci out of range" ); |
aoqi@0 | 485 | BasicBlock *block = _block_map->at(bci); |
aoqi@0 | 486 | // We may not be at the block start, so search backwards to find the block |
aoqi@0 | 487 | // containing bci. |
aoqi@0 | 488 | int t = bci; |
aoqi@0 | 489 | while (block == NULL && t > 0) { |
aoqi@0 | 490 | block = _block_map->at(--t); |
aoqi@0 | 491 | } |
aoqi@0 | 492 | assert( block != NULL, "invalid bytecode index; must be instruction index" ); |
aoqi@0 | 493 | assert(bci >= block->start_bci() && bci < block->limit_bci(), "block must contain bci."); |
aoqi@0 | 494 | |
aoqi@0 | 495 | answer = block->get_liveness_at(method(), bci); |
aoqi@0 | 496 | |
aoqi@0 | 497 | if (is_entry && method()->is_synchronized() && !method()->is_static()) { |
aoqi@0 | 498 | // Synchronized methods use the receiver once on entry. |
aoqi@0 | 499 | answer.at_put(0, true); |
aoqi@0 | 500 | } |
aoqi@0 | 501 | |
aoqi@0 | 502 | #ifndef PRODUCT |
aoqi@0 | 503 | if (TraceLivenessQuery) { |
aoqi@0 | 504 | tty->print("Liveness query of "); |
aoqi@0 | 505 | method()->print_short_name(); |
aoqi@0 | 506 | tty->print(" @ %d : result is ", bci); |
aoqi@0 | 507 | answer.print_on(tty); |
aoqi@0 | 508 | } |
aoqi@0 | 509 | |
aoqi@0 | 510 | if (TimeLivenessAnalysis) _time_query.stop(); |
aoqi@0 | 511 | if (TimeLivenessAnalysis) _time_total.stop(); |
aoqi@0 | 512 | #endif |
aoqi@0 | 513 | } |
aoqi@0 | 514 | |
aoqi@0 | 515 | #ifndef PRODUCT |
aoqi@0 | 516 | if (TimeLivenessAnalysis) { |
aoqi@0 | 517 | // Collect statistics. |
aoqi@0 | 518 | _total_locals_queried += _bit_map_size_bits; |
aoqi@0 | 519 | BitCounter counter; |
aoqi@0 | 520 | answer.iterate(&counter); |
aoqi@0 | 521 | _total_live_locals_queried += counter.count(); |
aoqi@0 | 522 | } |
aoqi@0 | 523 | #endif |
aoqi@0 | 524 | |
aoqi@0 | 525 | return answer; |
aoqi@0 | 526 | } |
aoqi@0 | 527 | |
aoqi@0 | 528 | |
aoqi@0 | 529 | #ifndef PRODUCT |
aoqi@0 | 530 | |
aoqi@0 | 531 | void MethodLiveness::print_times() { |
aoqi@0 | 532 | tty->print_cr ("Accumulated liveness analysis times/statistics:"); |
aoqi@0 | 533 | tty->print_cr ("-----------------------------------------------"); |
aoqi@0 | 534 | tty->print_cr (" Total : %3.3f sec.", _time_total.seconds()); |
aoqi@0 | 535 | tty->print_cr (" Build graph : %3.3f sec. (%2.2f%%)", _time_build_graph.seconds(), |
aoqi@0 | 536 | _time_build_graph.seconds() * 100 / _time_total.seconds()); |
aoqi@0 | 537 | tty->print_cr (" Gen / Kill : %3.3f sec. (%2.2f%%)", _time_gen_kill.seconds(), |
aoqi@0 | 538 | _time_gen_kill.seconds() * 100 / _time_total.seconds()); |
aoqi@0 | 539 | tty->print_cr (" Dataflow : %3.3f sec. (%2.2f%%)", _time_flow.seconds(), |
aoqi@0 | 540 | _time_flow.seconds() * 100 / _time_total.seconds()); |
aoqi@0 | 541 | tty->print_cr (" Query : %3.3f sec. (%2.2f%%)", _time_query.seconds(), |
aoqi@0 | 542 | _time_query.seconds() * 100 / _time_total.seconds()); |
aoqi@0 | 543 | tty->print_cr (" #bytes : %8d (%3.0f bytes per sec)", |
aoqi@0 | 544 | _total_bytes, |
aoqi@0 | 545 | _total_bytes / _time_total.seconds()); |
aoqi@0 | 546 | tty->print_cr (" #methods : %8d (%3.0f methods per sec)", |
aoqi@0 | 547 | _total_methods, |
aoqi@0 | 548 | _total_methods / _time_total.seconds()); |
aoqi@0 | 549 | tty->print_cr (" avg locals : %3.3f max locals : %3d", |
aoqi@0 | 550 | (float)_total_method_locals / _total_methods, |
aoqi@0 | 551 | _max_method_locals); |
aoqi@0 | 552 | tty->print_cr (" avg blocks : %3.3f max blocks : %3d", |
aoqi@0 | 553 | (float)_total_blocks / _total_methods, |
aoqi@0 | 554 | _max_method_blocks); |
aoqi@0 | 555 | tty->print_cr (" avg bytes : %3.3f", |
aoqi@0 | 556 | (float)_total_bytes / _total_methods); |
aoqi@0 | 557 | tty->print_cr (" #blocks : %8d", |
aoqi@0 | 558 | _total_blocks); |
aoqi@0 | 559 | tty->print_cr (" avg normal predecessors : %3.3f max normal predecessors : %3d", |
aoqi@0 | 560 | (float)_total_edges / _total_blocks, |
aoqi@0 | 561 | _max_block_edges); |
aoqi@0 | 562 | tty->print_cr (" avg exception predecessors : %3.3f max exception predecessors : %3d", |
aoqi@0 | 563 | (float)_total_exc_edges / _total_blocks, |
aoqi@0 | 564 | _max_block_exc_edges); |
aoqi@0 | 565 | tty->print_cr (" avg visits : %3.3f", |
aoqi@0 | 566 | (float)_total_visits / _total_blocks); |
aoqi@0 | 567 | tty->print_cr (" #locals queried : %8d #live : %8d %%live : %2.2f%%", |
aoqi@0 | 568 | _total_locals_queried, |
aoqi@0 | 569 | _total_live_locals_queried, |
aoqi@0 | 570 | 100.0 * _total_live_locals_queried / _total_locals_queried); |
aoqi@0 | 571 | } |
aoqi@0 | 572 | |
aoqi@0 | 573 | #endif |
aoqi@0 | 574 | |
aoqi@0 | 575 | |
aoqi@0 | 576 | MethodLiveness::BasicBlock::BasicBlock(MethodLiveness *analyzer, int start, int limit) : |
aoqi@0 | 577 | _gen((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()), |
aoqi@0 | 578 | analyzer->bit_map_size_bits()), |
aoqi@0 | 579 | _kill((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()), |
aoqi@0 | 580 | analyzer->bit_map_size_bits()), |
aoqi@0 | 581 | _entry((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()), |
aoqi@0 | 582 | analyzer->bit_map_size_bits()), |
aoqi@0 | 583 | _normal_exit((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()), |
aoqi@0 | 584 | analyzer->bit_map_size_bits()), |
aoqi@0 | 585 | _exception_exit((uintptr_t*)analyzer->arena()->Amalloc(BytesPerWord * analyzer->bit_map_size_words()), |
aoqi@0 | 586 | analyzer->bit_map_size_bits()), |
aoqi@0 | 587 | _last_bci(-1) { |
aoqi@0 | 588 | _analyzer = analyzer; |
aoqi@0 | 589 | _start_bci = start; |
aoqi@0 | 590 | _limit_bci = limit; |
aoqi@0 | 591 | _normal_predecessors = |
aoqi@0 | 592 | new (analyzer->arena()) GrowableArray<MethodLiveness::BasicBlock*>(analyzer->arena(), 5, 0, NULL); |
aoqi@0 | 593 | _exception_predecessors = |
aoqi@0 | 594 | new (analyzer->arena()) GrowableArray<MethodLiveness::BasicBlock*>(analyzer->arena(), 5, 0, NULL); |
aoqi@0 | 595 | _normal_exit.clear(); |
aoqi@0 | 596 | _exception_exit.clear(); |
aoqi@0 | 597 | _entry.clear(); |
aoqi@0 | 598 | |
aoqi@0 | 599 | // this initialization is not strictly necessary. |
aoqi@0 | 600 | // _gen and _kill are cleared at the beginning of compute_gen_kill_range() |
aoqi@0 | 601 | _gen.clear(); |
aoqi@0 | 602 | _kill.clear(); |
aoqi@0 | 603 | } |
aoqi@0 | 604 | |
aoqi@0 | 605 | |
aoqi@0 | 606 | |
aoqi@0 | 607 | MethodLiveness::BasicBlock *MethodLiveness::BasicBlock::split(int split_bci) { |
aoqi@0 | 608 | int start = _start_bci; |
aoqi@0 | 609 | int limit = _limit_bci; |
aoqi@0 | 610 | |
aoqi@0 | 611 | if (TraceLivenessGen) { |
aoqi@0 | 612 | tty->print_cr(" ** Splitting block (%d,%d) at %d", start, limit, split_bci); |
aoqi@0 | 613 | } |
aoqi@0 | 614 | |
aoqi@0 | 615 | GrowableArray<BasicBlock*>* save_predecessors = _normal_predecessors; |
aoqi@0 | 616 | |
aoqi@0 | 617 | assert (start < split_bci && split_bci < limit, "improper split"); |
aoqi@0 | 618 | |
aoqi@0 | 619 | // Make a new block to cover the first half of the range. |
aoqi@0 | 620 | BasicBlock *first_half = new (_analyzer->arena()) BasicBlock(_analyzer, start, split_bci); |
aoqi@0 | 621 | |
aoqi@0 | 622 | // Assign correct values to the second half (this) |
aoqi@0 | 623 | _normal_predecessors = first_half->_normal_predecessors; |
aoqi@0 | 624 | _start_bci = split_bci; |
aoqi@0 | 625 | add_normal_predecessor(first_half); |
aoqi@0 | 626 | |
aoqi@0 | 627 | // Assign correct predecessors to the new first half |
aoqi@0 | 628 | first_half->_normal_predecessors = save_predecessors; |
aoqi@0 | 629 | |
aoqi@0 | 630 | return first_half; |
aoqi@0 | 631 | } |
aoqi@0 | 632 | |
aoqi@0 | 633 | void MethodLiveness::BasicBlock::compute_gen_kill(ciMethod* method) { |
aoqi@0 | 634 | ciBytecodeStream bytes(method); |
aoqi@0 | 635 | bytes.reset_to_bci(start_bci()); |
aoqi@0 | 636 | bytes.set_max_bci(limit_bci()); |
aoqi@0 | 637 | compute_gen_kill_range(&bytes); |
aoqi@0 | 638 | |
aoqi@0 | 639 | } |
aoqi@0 | 640 | |
aoqi@0 | 641 | void MethodLiveness::BasicBlock::compute_gen_kill_range(ciBytecodeStream *bytes) { |
aoqi@0 | 642 | _gen.clear(); |
aoqi@0 | 643 | _kill.clear(); |
aoqi@0 | 644 | |
aoqi@0 | 645 | while (bytes->next() != ciBytecodeStream::EOBC()) { |
aoqi@0 | 646 | compute_gen_kill_single(bytes); |
aoqi@0 | 647 | } |
aoqi@0 | 648 | } |
aoqi@0 | 649 | |
aoqi@0 | 650 | void MethodLiveness::BasicBlock::compute_gen_kill_single(ciBytecodeStream *instruction) { |
aoqi@0 | 651 | int localNum; |
aoqi@0 | 652 | |
aoqi@0 | 653 | // We prohibit _gen and _kill from having locals in common. If we |
aoqi@0 | 654 | // know that one is definitely going to be applied before the other, |
aoqi@0 | 655 | // we could save some computation time by relaxing this prohibition. |
aoqi@0 | 656 | |
aoqi@0 | 657 | switch (instruction->cur_bc()) { |
aoqi@0 | 658 | case Bytecodes::_nop: |
aoqi@0 | 659 | case Bytecodes::_goto: |
aoqi@0 | 660 | case Bytecodes::_goto_w: |
aoqi@0 | 661 | case Bytecodes::_aconst_null: |
aoqi@0 | 662 | case Bytecodes::_new: |
aoqi@0 | 663 | case Bytecodes::_iconst_m1: |
aoqi@0 | 664 | case Bytecodes::_iconst_0: |
aoqi@0 | 665 | case Bytecodes::_iconst_1: |
aoqi@0 | 666 | case Bytecodes::_iconst_2: |
aoqi@0 | 667 | case Bytecodes::_iconst_3: |
aoqi@0 | 668 | case Bytecodes::_iconst_4: |
aoqi@0 | 669 | case Bytecodes::_iconst_5: |
aoqi@0 | 670 | case Bytecodes::_fconst_0: |
aoqi@0 | 671 | case Bytecodes::_fconst_1: |
aoqi@0 | 672 | case Bytecodes::_fconst_2: |
aoqi@0 | 673 | case Bytecodes::_bipush: |
aoqi@0 | 674 | case Bytecodes::_sipush: |
aoqi@0 | 675 | case Bytecodes::_lconst_0: |
aoqi@0 | 676 | case Bytecodes::_lconst_1: |
aoqi@0 | 677 | case Bytecodes::_dconst_0: |
aoqi@0 | 678 | case Bytecodes::_dconst_1: |
aoqi@0 | 679 | case Bytecodes::_ldc2_w: |
aoqi@0 | 680 | case Bytecodes::_ldc: |
aoqi@0 | 681 | case Bytecodes::_ldc_w: |
aoqi@0 | 682 | case Bytecodes::_iaload: |
aoqi@0 | 683 | case Bytecodes::_faload: |
aoqi@0 | 684 | case Bytecodes::_baload: |
aoqi@0 | 685 | case Bytecodes::_caload: |
aoqi@0 | 686 | case Bytecodes::_saload: |
aoqi@0 | 687 | case Bytecodes::_laload: |
aoqi@0 | 688 | case Bytecodes::_daload: |
aoqi@0 | 689 | case Bytecodes::_aaload: |
aoqi@0 | 690 | case Bytecodes::_iastore: |
aoqi@0 | 691 | case Bytecodes::_fastore: |
aoqi@0 | 692 | case Bytecodes::_bastore: |
aoqi@0 | 693 | case Bytecodes::_castore: |
aoqi@0 | 694 | case Bytecodes::_sastore: |
aoqi@0 | 695 | case Bytecodes::_lastore: |
aoqi@0 | 696 | case Bytecodes::_dastore: |
aoqi@0 | 697 | case Bytecodes::_aastore: |
aoqi@0 | 698 | case Bytecodes::_pop: |
aoqi@0 | 699 | case Bytecodes::_pop2: |
aoqi@0 | 700 | case Bytecodes::_dup: |
aoqi@0 | 701 | case Bytecodes::_dup_x1: |
aoqi@0 | 702 | case Bytecodes::_dup_x2: |
aoqi@0 | 703 | case Bytecodes::_dup2: |
aoqi@0 | 704 | case Bytecodes::_dup2_x1: |
aoqi@0 | 705 | case Bytecodes::_dup2_x2: |
aoqi@0 | 706 | case Bytecodes::_swap: |
aoqi@0 | 707 | case Bytecodes::_iadd: |
aoqi@0 | 708 | case Bytecodes::_fadd: |
aoqi@0 | 709 | case Bytecodes::_isub: |
aoqi@0 | 710 | case Bytecodes::_fsub: |
aoqi@0 | 711 | case Bytecodes::_imul: |
aoqi@0 | 712 | case Bytecodes::_fmul: |
aoqi@0 | 713 | case Bytecodes::_idiv: |
aoqi@0 | 714 | case Bytecodes::_fdiv: |
aoqi@0 | 715 | case Bytecodes::_irem: |
aoqi@0 | 716 | case Bytecodes::_frem: |
aoqi@0 | 717 | case Bytecodes::_ishl: |
aoqi@0 | 718 | case Bytecodes::_ishr: |
aoqi@0 | 719 | case Bytecodes::_iushr: |
aoqi@0 | 720 | case Bytecodes::_iand: |
aoqi@0 | 721 | case Bytecodes::_ior: |
aoqi@0 | 722 | case Bytecodes::_ixor: |
aoqi@0 | 723 | case Bytecodes::_l2f: |
aoqi@0 | 724 | case Bytecodes::_l2i: |
aoqi@0 | 725 | case Bytecodes::_d2f: |
aoqi@0 | 726 | case Bytecodes::_d2i: |
aoqi@0 | 727 | case Bytecodes::_fcmpl: |
aoqi@0 | 728 | case Bytecodes::_fcmpg: |
aoqi@0 | 729 | case Bytecodes::_ladd: |
aoqi@0 | 730 | case Bytecodes::_dadd: |
aoqi@0 | 731 | case Bytecodes::_lsub: |
aoqi@0 | 732 | case Bytecodes::_dsub: |
aoqi@0 | 733 | case Bytecodes::_lmul: |
aoqi@0 | 734 | case Bytecodes::_dmul: |
aoqi@0 | 735 | case Bytecodes::_ldiv: |
aoqi@0 | 736 | case Bytecodes::_ddiv: |
aoqi@0 | 737 | case Bytecodes::_lrem: |
aoqi@0 | 738 | case Bytecodes::_drem: |
aoqi@0 | 739 | case Bytecodes::_land: |
aoqi@0 | 740 | case Bytecodes::_lor: |
aoqi@0 | 741 | case Bytecodes::_lxor: |
aoqi@0 | 742 | case Bytecodes::_ineg: |
aoqi@0 | 743 | case Bytecodes::_fneg: |
aoqi@0 | 744 | case Bytecodes::_i2f: |
aoqi@0 | 745 | case Bytecodes::_f2i: |
aoqi@0 | 746 | case Bytecodes::_i2c: |
aoqi@0 | 747 | case Bytecodes::_i2s: |
aoqi@0 | 748 | case Bytecodes::_i2b: |
aoqi@0 | 749 | case Bytecodes::_lneg: |
aoqi@0 | 750 | case Bytecodes::_dneg: |
aoqi@0 | 751 | case Bytecodes::_l2d: |
aoqi@0 | 752 | case Bytecodes::_d2l: |
aoqi@0 | 753 | case Bytecodes::_lshl: |
aoqi@0 | 754 | case Bytecodes::_lshr: |
aoqi@0 | 755 | case Bytecodes::_lushr: |
aoqi@0 | 756 | case Bytecodes::_i2l: |
aoqi@0 | 757 | case Bytecodes::_i2d: |
aoqi@0 | 758 | case Bytecodes::_f2l: |
aoqi@0 | 759 | case Bytecodes::_f2d: |
aoqi@0 | 760 | case Bytecodes::_lcmp: |
aoqi@0 | 761 | case Bytecodes::_dcmpl: |
aoqi@0 | 762 | case Bytecodes::_dcmpg: |
aoqi@0 | 763 | case Bytecodes::_ifeq: |
aoqi@0 | 764 | case Bytecodes::_ifne: |
aoqi@0 | 765 | case Bytecodes::_iflt: |
aoqi@0 | 766 | case Bytecodes::_ifge: |
aoqi@0 | 767 | case Bytecodes::_ifgt: |
aoqi@0 | 768 | case Bytecodes::_ifle: |
aoqi@0 | 769 | case Bytecodes::_tableswitch: |
aoqi@0 | 770 | case Bytecodes::_ireturn: |
aoqi@0 | 771 | case Bytecodes::_freturn: |
aoqi@0 | 772 | case Bytecodes::_if_icmpeq: |
aoqi@0 | 773 | case Bytecodes::_if_icmpne: |
aoqi@0 | 774 | case Bytecodes::_if_icmplt: |
aoqi@0 | 775 | case Bytecodes::_if_icmpge: |
aoqi@0 | 776 | case Bytecodes::_if_icmpgt: |
aoqi@0 | 777 | case Bytecodes::_if_icmple: |
aoqi@0 | 778 | case Bytecodes::_lreturn: |
aoqi@0 | 779 | case Bytecodes::_dreturn: |
aoqi@0 | 780 | case Bytecodes::_if_acmpeq: |
aoqi@0 | 781 | case Bytecodes::_if_acmpne: |
aoqi@0 | 782 | case Bytecodes::_jsr: |
aoqi@0 | 783 | case Bytecodes::_jsr_w: |
aoqi@0 | 784 | case Bytecodes::_getstatic: |
aoqi@0 | 785 | case Bytecodes::_putstatic: |
aoqi@0 | 786 | case Bytecodes::_getfield: |
aoqi@0 | 787 | case Bytecodes::_putfield: |
aoqi@0 | 788 | case Bytecodes::_invokevirtual: |
aoqi@0 | 789 | case Bytecodes::_invokespecial: |
aoqi@0 | 790 | case Bytecodes::_invokestatic: |
aoqi@0 | 791 | case Bytecodes::_invokeinterface: |
aoqi@0 | 792 | case Bytecodes::_invokedynamic: |
aoqi@0 | 793 | case Bytecodes::_newarray: |
aoqi@0 | 794 | case Bytecodes::_anewarray: |
aoqi@0 | 795 | case Bytecodes::_checkcast: |
aoqi@0 | 796 | case Bytecodes::_arraylength: |
aoqi@0 | 797 | case Bytecodes::_instanceof: |
aoqi@0 | 798 | case Bytecodes::_athrow: |
aoqi@0 | 799 | case Bytecodes::_areturn: |
aoqi@0 | 800 | case Bytecodes::_monitorenter: |
aoqi@0 | 801 | case Bytecodes::_monitorexit: |
aoqi@0 | 802 | case Bytecodes::_ifnull: |
aoqi@0 | 803 | case Bytecodes::_ifnonnull: |
aoqi@0 | 804 | case Bytecodes::_multianewarray: |
aoqi@0 | 805 | case Bytecodes::_lookupswitch: |
aoqi@0 | 806 | // These bytecodes have no effect on the method's locals. |
aoqi@0 | 807 | break; |
aoqi@0 | 808 | |
aoqi@0 | 809 | case Bytecodes::_return: |
aoqi@0 | 810 | if (instruction->method()->intrinsic_id() == vmIntrinsics::_Object_init) { |
aoqi@0 | 811 | // return from Object.init implicitly registers a finalizer |
aoqi@0 | 812 | // for the receiver if needed, so keep it alive. |
aoqi@0 | 813 | load_one(0); |
aoqi@0 | 814 | } |
aoqi@0 | 815 | break; |
aoqi@0 | 816 | |
aoqi@0 | 817 | |
aoqi@0 | 818 | case Bytecodes::_lload: |
aoqi@0 | 819 | case Bytecodes::_dload: |
aoqi@0 | 820 | load_two(instruction->get_index()); |
aoqi@0 | 821 | break; |
aoqi@0 | 822 | |
aoqi@0 | 823 | case Bytecodes::_lload_0: |
aoqi@0 | 824 | case Bytecodes::_dload_0: |
aoqi@0 | 825 | load_two(0); |
aoqi@0 | 826 | break; |
aoqi@0 | 827 | |
aoqi@0 | 828 | case Bytecodes::_lload_1: |
aoqi@0 | 829 | case Bytecodes::_dload_1: |
aoqi@0 | 830 | load_two(1); |
aoqi@0 | 831 | break; |
aoqi@0 | 832 | |
aoqi@0 | 833 | case Bytecodes::_lload_2: |
aoqi@0 | 834 | case Bytecodes::_dload_2: |
aoqi@0 | 835 | load_two(2); |
aoqi@0 | 836 | break; |
aoqi@0 | 837 | |
aoqi@0 | 838 | case Bytecodes::_lload_3: |
aoqi@0 | 839 | case Bytecodes::_dload_3: |
aoqi@0 | 840 | load_two(3); |
aoqi@0 | 841 | break; |
aoqi@0 | 842 | |
aoqi@0 | 843 | case Bytecodes::_iload: |
aoqi@0 | 844 | case Bytecodes::_iinc: |
aoqi@0 | 845 | case Bytecodes::_fload: |
aoqi@0 | 846 | case Bytecodes::_aload: |
aoqi@0 | 847 | case Bytecodes::_ret: |
aoqi@0 | 848 | load_one(instruction->get_index()); |
aoqi@0 | 849 | break; |
aoqi@0 | 850 | |
aoqi@0 | 851 | case Bytecodes::_iload_0: |
aoqi@0 | 852 | case Bytecodes::_fload_0: |
aoqi@0 | 853 | case Bytecodes::_aload_0: |
aoqi@0 | 854 | load_one(0); |
aoqi@0 | 855 | break; |
aoqi@0 | 856 | |
aoqi@0 | 857 | case Bytecodes::_iload_1: |
aoqi@0 | 858 | case Bytecodes::_fload_1: |
aoqi@0 | 859 | case Bytecodes::_aload_1: |
aoqi@0 | 860 | load_one(1); |
aoqi@0 | 861 | break; |
aoqi@0 | 862 | |
aoqi@0 | 863 | case Bytecodes::_iload_2: |
aoqi@0 | 864 | case Bytecodes::_fload_2: |
aoqi@0 | 865 | case Bytecodes::_aload_2: |
aoqi@0 | 866 | load_one(2); |
aoqi@0 | 867 | break; |
aoqi@0 | 868 | |
aoqi@0 | 869 | case Bytecodes::_iload_3: |
aoqi@0 | 870 | case Bytecodes::_fload_3: |
aoqi@0 | 871 | case Bytecodes::_aload_3: |
aoqi@0 | 872 | load_one(3); |
aoqi@0 | 873 | break; |
aoqi@0 | 874 | |
aoqi@0 | 875 | case Bytecodes::_lstore: |
aoqi@0 | 876 | case Bytecodes::_dstore: |
aoqi@0 | 877 | store_two(localNum = instruction->get_index()); |
aoqi@0 | 878 | break; |
aoqi@0 | 879 | |
aoqi@0 | 880 | case Bytecodes::_lstore_0: |
aoqi@0 | 881 | case Bytecodes::_dstore_0: |
aoqi@0 | 882 | store_two(0); |
aoqi@0 | 883 | break; |
aoqi@0 | 884 | |
aoqi@0 | 885 | case Bytecodes::_lstore_1: |
aoqi@0 | 886 | case Bytecodes::_dstore_1: |
aoqi@0 | 887 | store_two(1); |
aoqi@0 | 888 | break; |
aoqi@0 | 889 | |
aoqi@0 | 890 | case Bytecodes::_lstore_2: |
aoqi@0 | 891 | case Bytecodes::_dstore_2: |
aoqi@0 | 892 | store_two(2); |
aoqi@0 | 893 | break; |
aoqi@0 | 894 | |
aoqi@0 | 895 | case Bytecodes::_lstore_3: |
aoqi@0 | 896 | case Bytecodes::_dstore_3: |
aoqi@0 | 897 | store_two(3); |
aoqi@0 | 898 | break; |
aoqi@0 | 899 | |
aoqi@0 | 900 | case Bytecodes::_istore: |
aoqi@0 | 901 | case Bytecodes::_fstore: |
aoqi@0 | 902 | case Bytecodes::_astore: |
aoqi@0 | 903 | store_one(instruction->get_index()); |
aoqi@0 | 904 | break; |
aoqi@0 | 905 | |
aoqi@0 | 906 | case Bytecodes::_istore_0: |
aoqi@0 | 907 | case Bytecodes::_fstore_0: |
aoqi@0 | 908 | case Bytecodes::_astore_0: |
aoqi@0 | 909 | store_one(0); |
aoqi@0 | 910 | break; |
aoqi@0 | 911 | |
aoqi@0 | 912 | case Bytecodes::_istore_1: |
aoqi@0 | 913 | case Bytecodes::_fstore_1: |
aoqi@0 | 914 | case Bytecodes::_astore_1: |
aoqi@0 | 915 | store_one(1); |
aoqi@0 | 916 | break; |
aoqi@0 | 917 | |
aoqi@0 | 918 | case Bytecodes::_istore_2: |
aoqi@0 | 919 | case Bytecodes::_fstore_2: |
aoqi@0 | 920 | case Bytecodes::_astore_2: |
aoqi@0 | 921 | store_one(2); |
aoqi@0 | 922 | break; |
aoqi@0 | 923 | |
aoqi@0 | 924 | case Bytecodes::_istore_3: |
aoqi@0 | 925 | case Bytecodes::_fstore_3: |
aoqi@0 | 926 | case Bytecodes::_astore_3: |
aoqi@0 | 927 | store_one(3); |
aoqi@0 | 928 | break; |
aoqi@0 | 929 | |
aoqi@0 | 930 | case Bytecodes::_wide: |
aoqi@0 | 931 | fatal("Iterator should skip this bytecode"); |
aoqi@0 | 932 | break; |
aoqi@0 | 933 | |
aoqi@0 | 934 | default: |
aoqi@0 | 935 | tty->print("unexpected opcode: %d\n", instruction->cur_bc()); |
aoqi@0 | 936 | ShouldNotReachHere(); |
aoqi@0 | 937 | break; |
aoqi@0 | 938 | } |
aoqi@0 | 939 | } |
aoqi@0 | 940 | |
aoqi@0 | 941 | void MethodLiveness::BasicBlock::load_two(int local) { |
aoqi@0 | 942 | load_one(local); |
aoqi@0 | 943 | load_one(local+1); |
aoqi@0 | 944 | } |
aoqi@0 | 945 | |
aoqi@0 | 946 | void MethodLiveness::BasicBlock::load_one(int local) { |
aoqi@0 | 947 | if (!_kill.at(local)) { |
aoqi@0 | 948 | _gen.at_put(local, true); |
aoqi@0 | 949 | } |
aoqi@0 | 950 | } |
aoqi@0 | 951 | |
aoqi@0 | 952 | void MethodLiveness::BasicBlock::store_two(int local) { |
aoqi@0 | 953 | store_one(local); |
aoqi@0 | 954 | store_one(local+1); |
aoqi@0 | 955 | } |
aoqi@0 | 956 | |
aoqi@0 | 957 | void MethodLiveness::BasicBlock::store_one(int local) { |
aoqi@0 | 958 | if (!_gen.at(local)) { |
aoqi@0 | 959 | _kill.at_put(local, true); |
aoqi@0 | 960 | } |
aoqi@0 | 961 | } |
aoqi@0 | 962 | |
aoqi@0 | 963 | void MethodLiveness::BasicBlock::propagate(MethodLiveness *ml) { |
aoqi@0 | 964 | // These set operations could be combined for efficiency if the |
aoqi@0 | 965 | // performance of this analysis becomes an issue. |
aoqi@0 | 966 | _entry.set_union(_normal_exit); |
aoqi@0 | 967 | _entry.set_difference(_kill); |
aoqi@0 | 968 | _entry.set_union(_gen); |
aoqi@0 | 969 | |
aoqi@0 | 970 | // Note that we merge information from our exceptional successors |
aoqi@0 | 971 | // just once, rather than at individual bytecodes. |
aoqi@0 | 972 | _entry.set_union(_exception_exit); |
aoqi@0 | 973 | |
aoqi@0 | 974 | if (TraceLivenessGen) { |
aoqi@0 | 975 | tty->print_cr(" ** Visiting block at %d **", start_bci()); |
aoqi@0 | 976 | print_on(tty); |
aoqi@0 | 977 | } |
aoqi@0 | 978 | |
aoqi@0 | 979 | int i; |
aoqi@0 | 980 | for (i=_normal_predecessors->length()-1; i>=0; i--) { |
aoqi@0 | 981 | BasicBlock *block = _normal_predecessors->at(i); |
aoqi@0 | 982 | if (block->merge_normal(_entry)) { |
aoqi@0 | 983 | ml->work_list_add(block); |
aoqi@0 | 984 | } |
aoqi@0 | 985 | } |
aoqi@0 | 986 | for (i=_exception_predecessors->length()-1; i>=0; i--) { |
aoqi@0 | 987 | BasicBlock *block = _exception_predecessors->at(i); |
aoqi@0 | 988 | if (block->merge_exception(_entry)) { |
aoqi@0 | 989 | ml->work_list_add(block); |
aoqi@0 | 990 | } |
aoqi@0 | 991 | } |
aoqi@0 | 992 | } |
aoqi@0 | 993 | |
aoqi@0 | 994 | bool MethodLiveness::BasicBlock::merge_normal(BitMap other) { |
aoqi@0 | 995 | return _normal_exit.set_union_with_result(other); |
aoqi@0 | 996 | } |
aoqi@0 | 997 | |
aoqi@0 | 998 | bool MethodLiveness::BasicBlock::merge_exception(BitMap other) { |
aoqi@0 | 999 | return _exception_exit.set_union_with_result(other); |
aoqi@0 | 1000 | } |
aoqi@0 | 1001 | |
aoqi@0 | 1002 | MethodLivenessResult MethodLiveness::BasicBlock::get_liveness_at(ciMethod* method, int bci) { |
aoqi@0 | 1003 | MethodLivenessResult answer(NEW_RESOURCE_ARRAY(uintptr_t, _analyzer->bit_map_size_words()), |
aoqi@0 | 1004 | _analyzer->bit_map_size_bits()); |
aoqi@0 | 1005 | answer.set_is_valid(); |
aoqi@0 | 1006 | |
aoqi@0 | 1007 | #ifndef ASSERT |
aoqi@0 | 1008 | if (bci == start_bci()) { |
aoqi@0 | 1009 | answer.set_from(_entry); |
aoqi@0 | 1010 | return answer; |
aoqi@0 | 1011 | } |
aoqi@0 | 1012 | #endif |
aoqi@0 | 1013 | |
aoqi@0 | 1014 | #ifdef ASSERT |
aoqi@0 | 1015 | ResourceMark rm; |
aoqi@0 | 1016 | BitMap g(_gen.size()); g.set_from(_gen); |
aoqi@0 | 1017 | BitMap k(_kill.size()); k.set_from(_kill); |
aoqi@0 | 1018 | #endif |
aoqi@0 | 1019 | if (_last_bci != bci || trueInDebug) { |
aoqi@0 | 1020 | ciBytecodeStream bytes(method); |
aoqi@0 | 1021 | bytes.reset_to_bci(bci); |
aoqi@0 | 1022 | bytes.set_max_bci(limit_bci()); |
aoqi@0 | 1023 | compute_gen_kill_range(&bytes); |
aoqi@0 | 1024 | assert(_last_bci != bci || |
aoqi@0 | 1025 | (g.is_same(_gen) && k.is_same(_kill)), "cached computation is incorrect"); |
aoqi@0 | 1026 | _last_bci = bci; |
aoqi@0 | 1027 | } |
aoqi@0 | 1028 | |
aoqi@0 | 1029 | answer.clear(); |
aoqi@0 | 1030 | answer.set_union(_normal_exit); |
aoqi@0 | 1031 | answer.set_difference(_kill); |
aoqi@0 | 1032 | answer.set_union(_gen); |
aoqi@0 | 1033 | answer.set_union(_exception_exit); |
aoqi@0 | 1034 | |
aoqi@0 | 1035 | #ifdef ASSERT |
aoqi@0 | 1036 | if (bci == start_bci()) { |
aoqi@0 | 1037 | assert(answer.is_same(_entry), "optimized answer must be accurate"); |
aoqi@0 | 1038 | } |
aoqi@0 | 1039 | #endif |
aoqi@0 | 1040 | |
aoqi@0 | 1041 | return answer; |
aoqi@0 | 1042 | } |
aoqi@0 | 1043 | |
aoqi@0 | 1044 | #ifndef PRODUCT |
aoqi@0 | 1045 | |
aoqi@0 | 1046 | void MethodLiveness::BasicBlock::print_on(outputStream *os) const { |
aoqi@0 | 1047 | os->print_cr("==================================================================="); |
aoqi@0 | 1048 | os->print_cr(" Block start: %4d, limit: %4d", _start_bci, _limit_bci); |
aoqi@0 | 1049 | os->print (" Normal predecessors (%2d) @", _normal_predecessors->length()); |
aoqi@0 | 1050 | int i; |
aoqi@0 | 1051 | for (i=0; i < _normal_predecessors->length(); i++) { |
aoqi@0 | 1052 | os->print(" %4d", _normal_predecessors->at(i)->start_bci()); |
aoqi@0 | 1053 | } |
aoqi@0 | 1054 | os->cr(); |
aoqi@0 | 1055 | os->print (" Exceptional predecessors (%2d) @", _exception_predecessors->length()); |
aoqi@0 | 1056 | for (i=0; i < _exception_predecessors->length(); i++) { |
aoqi@0 | 1057 | os->print(" %4d", _exception_predecessors->at(i)->start_bci()); |
aoqi@0 | 1058 | } |
aoqi@0 | 1059 | os->cr(); |
aoqi@0 | 1060 | os->print (" Normal Exit : "); |
aoqi@0 | 1061 | _normal_exit.print_on(os); |
aoqi@0 | 1062 | os->print (" Gen : "); |
aoqi@0 | 1063 | _gen.print_on(os); |
aoqi@0 | 1064 | os->print (" Kill : "); |
aoqi@0 | 1065 | _kill.print_on(os); |
aoqi@0 | 1066 | os->print (" Exception Exit: "); |
aoqi@0 | 1067 | _exception_exit.print_on(os); |
aoqi@0 | 1068 | os->print (" Entry : "); |
aoqi@0 | 1069 | _entry.print_on(os); |
aoqi@0 | 1070 | } |
aoqi@0 | 1071 | |
aoqi@0 | 1072 | #endif // PRODUCT |