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 25 // The MethodLiveness class performs a simple liveness analysis on a method 26 // in order to decide which locals are live (that is, will be used again) at 27 // a particular bytecode index (bci). 28 // 29 // The algorithm goes: 30 // 31 // 1. Break the method into a set of basic blocks. For each basic block we 32 // also keep track of its set of predecessors through normal control flow 33 // and predecessors through exceptional control flow. 34 // 35 // 2. For each basic block, compute two sets, gen (the set of values used before 36 // they are defined) and kill (the set of values defined before they are used) 37 // in the basic block. A basic block "needs" the locals in its gen set to 38 // perform its computation. A basic block "provides" values for the locals in 39 // its kill set, allowing a need from a successor to be ignored. 40 // 41 // 3. Liveness information (the set of locals which are needed) is pushed backwards through 42 // the program, from blocks to their predecessors. We compute and store liveness 43 // information for the normal/exceptional exit paths for each basic block. When 44 // this process reaches a fixed point, we are done. 45 // 46 // 4. When we are asked about the liveness at a particular bci with a basic block, we 47 // compute gen/kill sets which represent execution from that bci to the exit of 48 // its blocks. We then compose this range gen/kill information with the normal 49 // and exceptional exit information for the block to produce liveness information 50 // at that bci. 51 // 52 // The algorithm is approximate in many respects. Notably: 53 // 54 // 1. We do not do the analysis necessary to match jsr's with the appropriate ret. 55 // Instead we make the conservative assumption that any ret can return to any 56 // jsr return site. 57 // 2. Instead of computing the effects of exceptions at every instruction, we 58 // summarize the effects of all exceptional continuations from the block as 59 // a single set (_exception_exit), losing some information but simplifying the 60 // analysis. 61 62 63 # include "incls/_precompiled.incl" 64 # include "incls/_methodLiveness.cpp.incl" 65 66 //-------------------------------------------------------------------------- 67 // The BitCounter class is used for counting the number of bits set in 68 // some BitMap. It is only used when collecting liveness statistics. 69 70 #ifndef PRODUCT 71 72 class BitCounter: public BitMapClosure { 73 private: 74 int _count; 75 public: 76 BitCounter() : _count(0) {} 77 78 // Callback when bit in map is set 79 virtual bool do_bit(size_t offset) { 80 _count++; 81 return true; 82 } 83 84 int count() { 85 return _count; | 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 #include "precompiled.hpp" 26 #include "ci/ciMethod.hpp" 27 #include "ci/ciMethodBlocks.hpp" 28 #include "ci/ciStreams.hpp" 29 #include "compiler/methodLiveness.hpp" 30 #include "interpreter/bytecode.hpp" 31 #include "interpreter/bytecodes.hpp" 32 #include "memory/allocation.inline.hpp" 33 #include "utilities/bitMap.inline.hpp" 34 35 // The MethodLiveness class performs a simple liveness analysis on a method 36 // in order to decide which locals are live (that is, will be used again) at 37 // a particular bytecode index (bci). 38 // 39 // The algorithm goes: 40 // 41 // 1. Break the method into a set of basic blocks. For each basic block we 42 // also keep track of its set of predecessors through normal control flow 43 // and predecessors through exceptional control flow. 44 // 45 // 2. For each basic block, compute two sets, gen (the set of values used before 46 // they are defined) and kill (the set of values defined before they are used) 47 // in the basic block. A basic block "needs" the locals in its gen set to 48 // perform its computation. A basic block "provides" values for the locals in 49 // its kill set, allowing a need from a successor to be ignored. 50 // 51 // 3. Liveness information (the set of locals which are needed) is pushed backwards through 52 // the program, from blocks to their predecessors. We compute and store liveness 53 // information for the normal/exceptional exit paths for each basic block. When 54 // this process reaches a fixed point, we are done. 55 // 56 // 4. When we are asked about the liveness at a particular bci with a basic block, we 57 // compute gen/kill sets which represent execution from that bci to the exit of 58 // its blocks. We then compose this range gen/kill information with the normal 59 // and exceptional exit information for the block to produce liveness information 60 // at that bci. 61 // 62 // The algorithm is approximate in many respects. Notably: 63 // 64 // 1. We do not do the analysis necessary to match jsr's with the appropriate ret. 65 // Instead we make the conservative assumption that any ret can return to any 66 // jsr return site. 67 // 2. Instead of computing the effects of exceptions at every instruction, we 68 // summarize the effects of all exceptional continuations from the block as 69 // a single set (_exception_exit), losing some information but simplifying the 70 // analysis. 71 72 73 //-------------------------------------------------------------------------- 74 // The BitCounter class is used for counting the number of bits set in 75 // some BitMap. It is only used when collecting liveness statistics. 76 77 #ifndef PRODUCT 78 79 class BitCounter: public BitMapClosure { 80 private: 81 int _count; 82 public: 83 BitCounter() : _count(0) {} 84 85 // Callback when bit in map is set 86 virtual bool do_bit(size_t offset) { 87 _count++; 88 return true; 89 } 90 91 int count() { 92 return _count; |